Submission #501516

#	Time	Username	Problem	Language	Result	Execution time	Memory
501516		doowey	Ideal city (IOI12_city)	C++14	100 / 100	52 ms	19136 KiB

city

#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 (stderr)

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45