Submission #296217

#	Time	Username	Problem	Language	Result	Execution time	Memory
296217		alexandra_udristoiu	Ideal city (IOI12_city)	C++14	100 / 100	60 ms	9208 KiB

city

#include<iostream>
#include<algorithm>
#include<vector>
#define x first
#define y second
#define DIM 100005
#define mod 1000000000
using namespace std;
static int n, sol, d[DIM], num[DIM];
static pair<int, int> p[DIM];
static vector<int> v[DIM];
struct str{
    int pos, p, u;
};
str w[DIM];
void dfs(int nod, int t){
    d[nod] = 0;
    num[nod] = w[nod].u - w[nod].p + 1;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(vecin == t){
            continue;
        }
        dfs(vecin, nod);
        sol = (sol + num[nod] * 1LL * (d[vecin] + num[vecin]) ) % mod;
        sol = (sol + num[vecin] * 1LL * d[nod]) % mod;
        d[nod] += d[vecin] + num[vecin];
        num[nod] += num[vecin];
    }
}
void solve(){
    int i, j, nr = 0;
    sort(p + 1, p + n + 1);
    for(i = 1; i <= n; i++){
        nr++;
        w[nr].pos = p[i].x;
        w[nr].p = p[i].y;
        for(j = i + 1; j <= n; j++){
            if(p[j].x != p[i].x || p[j].y != p[j - 1].y + 1){
                break;
            }
        }
        j--;
        w[nr].u = p[j].y;
        i = j;
    }
    j = 1;
    for(i = 1; i <= nr; i++){
        while(j < i && w[j].pos + 1 < w[i].pos || (w[j].pos + 1 == w[i].pos && w[j].u < w[i].p) ){
            j++;
        }
        while(j < i && w[j].pos + 1 == w[i].pos && max(w[i].p, w[j].p) <= min(w[i].u, w[j].u) ){
            v[i].push_back(j);
            v[j].push_back(i);
            j++;
        }
        j--;
    }
    dfs(1, 0);
}

int DistanceSum(int N, int *X, int *Y) {
    int i;
    n = N;
    for(i = 1; i <= n; i++){
        p[i] = make_pair(X[i - 1], Y[i - 1]);
    }
    solve();
    for(i = 1; i <= n; i++){
        v[i].clear();
    }
    for(i = 1; i <= n; i++){
        p[i] = make_pair(Y[i - 1], X[i - 1]);
    }
    solve();
    return sol;
}

Compilation message (stderr)

city.cpp: In function 'void dfs(int, int)':
city.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
city.cpp: In function 'void solve()':
city.cpp:49:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   49 |         while(j < i && w[j].pos + 1 < w[i].pos || (w[j].pos + 1 == w[i].pos && w[j].u < w[i].p) ){
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45