Codeforces Contest 624

Dashboard - AIM Tech Round (Div. 2) - Codeforces

pA. Print ( L - d ) / ( v1 + v2 ).

#include <bits/stdc++.h>
using namespace std;

int main(){
    int d, L, v1, v2;
    scanf("%d %d %d %d", &d, &L, &v1, &v2);
    double dis = (double)L - d;
    double vel = (double)v1 + v2;
    printf("%.7lf\n", dis / vel);
    return 0;
}

pB. Sort a from large to small, then push down numbers that are duplicates. Note that long long is required.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 26 + 1;

int n;
int a[MAXN];

int main(){
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    sort( a, a + n, greater<int>() );
    ll ans = a[0], pre = a[0], cnt = 0;
    for(int i = 1; i < n; ++i){
        if( a[i] == pre ) ++cnt;
        else{
            ans += a[i];
            for(int k = pre - 1; k > a[i]; --k){
                if( cnt == 0 ) break;
                ans += k, --cnt;
            }
        }
        pre = a[i];
    }
    if( a[n - 1] > 1 && cnt > 0 ){
        for(int k = a[n - 1] - 1; k >= 1; --k){
            if( cnt == 0 ) break;
            ans += k, --cnt;
        }
    }
    cout << ans << endl;
    return 0;
}

pC. According to the description, we will find that 'b' must be connected to all other nodes. Then we find out that 'a's and 'c's have bipartite relation when we build edges for only all 'a' <-> 'c' ( this can be done easily by constructing edges on where edges do not exist ), because only edges of 'a' <-> 'c' will not appear in the given graph. At last, check that everything is valid before output.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 5;
const int MAXM = 500 * 499 / 2 + 5;

int n, m;
vector<int> G[MAXN];
int adj[MAXN][MAXN], acadj[MAXN][MAXN];
int col[MAXN]; // 1: a, 2: b, 3: c

bool bipart(int u){
    for(int v = 1; v <= n; ++v)
        if( acadj[u][v] ){
            if( col[v] == col[u] ) return false;
            if( !col[v] ){
                col[v] = 4 - col[u];
                if( !bipart( v ) ) return false;
            }
        }
    return true;
}

bool check(){
    for(int u = 1; u <= n; ++u)
        if( !col[u] )
            return false;
    for(int u = 1; u <= n; ++u)
        for(int v = 1; v <= n; ++v) if( u != v )
            if( !acadj[u][v] )
                if( abs( col[u] - col[v] ) > 1 )
                    return false;
    return true;
}

void print(){
    for(int u = 1; u <= n; ++u)
        printf("%c", (char)( 'a' + col[u] - 1 ));
    puts("");
}

void solve(){
    for(int u = 1; u <= n; ++u)
        if( G[u].size() == n - 1 )
            col[u] = 2;
    bool can_bip = true;
    for(int u = 1; u <= n; ++u)
        if( !col[u] ){
            col[u] = 1;
            can_bip = bipart( u );
            break;
        }
    if( can_bip && check() ) puts("Yes"), print();
    else puts("No");
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i){
        int u, v; scanf("%d %d", &u, &v);
        G[u].push_back( v ); // 1 - indexed
        G[v].push_back( u );
        adj[u][v] = adj[v][u] = 1;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            if( !adj[i][j] )
                acadj[i][j] = acadj[j][i] = 1;
    solve();
    return 0;
}