oj.uz

Submission #501516

# Submission time Handle Problem Language Result Execution time Memory
501516 2022-01-03T18:18:54 Z doowey Ideal city (IOI12_city) C++14
100 / 100
 52 ms 19136 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 100;
int n;
vector<pii> C;

vector<int> I[N];
vector<int> id[N];
vector<int> G[N];
int cnt[N];
int og[N];

void add_edge(int u, int v){
    if(!G[u].empty() && G[u].back() == v) return;
    G[u].push_back(v);
    G[v].push_back(u);
}

ll cum[N];

void dfs(int u, int par){
    for(auto x : G[u]){
        if(x == par) continue;
        dfs(x, u);
        cnt[u] += cnt[x];
        cum[u] += cum[x] + cnt[x];
    }
}

ll dp[N];

void reroot(int u, int par){
    int ua;
    ll ub;
    int va;
    ll vb;
    dp[u] = cum[u];

    for(auto x : G[u]){
        if(x == par) continue;
        ua = cnt[u];
        ub = cum[u];
        va = cnt[x];
        vb = cum[x];

        cnt[u] -= cnt[x];
        cum[u] -= cum[x] + cnt[x];

        cnt[x] += cnt[u];
        cum[x] += cum[u] + cnt[u];
        reroot(x, u);

        cnt[u] = ua;
        cum[u] = ub;
        cnt[x] = va;
        cum[x] = vb;
    }
}

ll construct_graph(){
    for(int i = 0 ; i < N; i ++ ){
        I[i].clear();
        id[i].clear();
        G[i].clear();
        cnt[i] = 0;
        cum[i]=0;
        dp[i]=0;
        og[i]=0;
    }
    for(auto x : C){
        I[x.fi].push_back(x.se);
    }
    int cur_id = 0;
    int las;
    for(int i = 0 ; i < N; i ++ ){
        if(I[i].empty()) break;
        sort(I[i].begin(), I[i].end());
        las = 0;
        for(int j = 0 ; j < I[i].size(); j ++ ){
            if(j == 0 || I[i][j] != I[i][j - 1] + 1){
                cur_id ++ ;
            }
            cnt[cur_id] ++ ;
            og[cur_id] ++ ;
            id[i].push_back(cur_id);
            if(i > 0 && !I[i-1].empty()){
                while(las < I[i-1].size() && I[i-1][las] < I[i][j]){
                    las ++ ;
                }
                if(las < I[i-1].size() && I[i][j] == I[i-1][las]){
                    add_edge(id[i][j], id[i-1][las]);
                }
            }
        }
    }
    dfs(1,-1);
    reroot(1,-1);
    ll res = 0;
    for(int i = 1; i <= cur_id; i ++ ){
        res += og[i] * 1ll * dp[i];
    }
    return res;
}

int DistanceSum(int _n, int *X, int *Y) {
    n = _n;
    for(int i = 0 ; i < n; i ++ ){
        C.push_back(mp(X[i], Y[i]));
    }
    int lowx = X[0];
    int lowy = Y[0];
    for(int i = 0 ; i < n; i ++ ){
        lowx = min(lowx, C[i].fi);
        lowy = min(lowy, C[i].se);
    }
    for(auto &x : C){
        x.fi -= lowx;
        x.se -= lowy;
    }
    ll soln = construct_graph();
    for(auto &x : C){
        swap(x.fi, x.se);
    }
    soln += construct_graph();
    soln /= 2ll;
    soln %= (ll)1e9;
    return soln;

}

Compilation message

city.cpp: In function 'll construct_graph()':
city.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int j = 0 ; j < I[i].size(); j ++ ){
      |                         ~~^~~~~~~~~~~~~
city.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 while(las < I[i-1].size() && I[i-1][las] < I[i][j]){
      |                       ~~~~^~~~~~~~~~~~~~~
city.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                 if(las < I[i-1].size() && I[i][j] == I[i-1][las]){
      |                    ~~~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10540 KB Output is correct
2 Correct 11 ms 10804 KB Output is correct
3 Correct 22 ms 11596 KB Output is correct
4 Correct 20 ms 12100 KB Output is correct
5 Correct 35 ms 13616 KB Output is correct
6 Correct 33 ms 14632 KB Output is correct
7 Correct 33 ms 14472 KB Output is correct
8 Correct 39 ms 13356 KB Output is correct
9 Correct 34 ms 14396 KB Output is correct
10 Correct 52 ms 19136 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10932 KB Output is correct
2 Correct 13 ms 10868 KB Output is correct
3 Correct 29 ms 12468 KB Output is correct
4 Correct 24 ms 12320 KB Output is correct
5 Correct 49 ms 15536 KB Output is correct
6 Correct 42 ms 14392 KB Output is correct
7 Correct 47 ms 15024 KB Output is correct
8 Correct 38 ms 14764 KB Output is correct
9 Correct 47 ms 13692 KB Output is correct
10 Correct 42 ms 14240 KB Output is correct