oj.uz

Submission #296217

# Submission time Handle Problem Language Result Execution time Memory
296217 2020-09-10T12:17:54 Z alexandra_udristoiu Ideal city (IOI12_city) C++14
100 / 100
 60 ms 9208 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 3 ms 2688 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3200 KB Output is correct
2 Correct 10 ms 3328 KB Output is correct
3 Correct 24 ms 4008 KB Output is correct
4 Correct 22 ms 3968 KB Output is correct
5 Correct 45 ms 5240 KB Output is correct
6 Correct 46 ms 5240 KB Output is correct
7 Correct 46 ms 5504 KB Output is correct
8 Correct 46 ms 5248 KB Output is correct
9 Correct 48 ms 5504 KB Output is correct
10 Correct 54 ms 9208 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3712 KB Output is correct
2 Correct 12 ms 3584 KB Output is correct
3 Correct 29 ms 4984 KB Output is correct
4 Correct 27 ms 4736 KB Output is correct
5 Correct 58 ms 7288 KB Output is correct
6 Correct 49 ms 6136 KB Output is correct
7 Correct 60 ms 7416 KB Output is correct
8 Correct 50 ms 6168 KB Output is correct
9 Correct 49 ms 5752 KB Output is correct
10 Correct 47 ms 5760 KB Output is correct