Submission #97726

#	Time	Username	Problem	Language	Result	Execution time	Memory
97726		TAMREF	Ideal city (IOI12_city)	C++11	100 / 100	190 ms	21436 KiB

city

#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define emp emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
using ll = long long;
using lf = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

const int mx = 1e5 + 5;
const ll mod = 1e9;
pii P[mx];
int n;
int rep[mx];
ll sz[mx], dep[mx];
ll ss[mx], sds[mx];
bool vis[mx];
vector<int> G[mx], C[mx];

int f(int x){
    return x == rep[x] ? x : rep[x] = f(rep[x]);
}

void c(int x, int y){
    x = f(x); y = f(y);
    if(x != y){
        rep[y] = x;
        sz[x] += sz[y];
    }
}

unordered_map<ll,int> S;

void dfsi(int x){
    vis[x] = 1;
    for(int u : G[x]){
        if(vis[u]) continue;
        C[x].push_back(u);
        dep[u] = dep[x] + 1;
        dfsi(u);
    }
}

ll dis;
void dfs(int x){
    ll SS = sz[x], SSQ = sz[x] * sz[x] % mod, SDS = sz[x] * dep[x] % mod, SDSQ = sz[x] * sz[x] * dep[x] % mod;
    for(int u : C[x]){
        dfs(u);
        SS += ss[u]; SS %= mod;
        SSQ += ss[u] * ss[u] % mod; SSQ %= mod;
        SDS += sds[u]; SDS %= mod;
        SDSQ += sds[u] * ss[u] % mod; SDSQ %= mod;
    }
    //printf("dfs on %d : ss = %lld, ssq = %lld, sds = %lld, sdsq = %lld\n",x,ss[x],ssq[x],sds[x],sdsq[x]);
    dis += SDS * SS % mod - SDSQ - dep[x] * (SS * SS % mod - SSQ) % mod;
    dis = (dis % mod + mod) % mod;
    ss[x] = SS;
    sds[x] = SDS;
    //printf("dis = %lld\n",dis);
}

ll pro(){
    iota(rep,rep+n,0);
    fill(sz,sz+n,1);
    fill(sds,sds+n,0);
    fill(ss,ss+n,0);
    fill(dep,dep+n,0);
    fill(vis,vis+n,0);
    S.clear();
    dis = 0;
    for(int i = 0; i < n; i++) G[i].clear(), C[i].clear();

    sort(P,P+n);
    int cur = 0;
    for(int i = 0; i < n; i++) S[ll(P[i].va) << 32 | P[i].vb] = i;
    for(int i = 1; i < n; i++){
        if(P[cur].va != P[i].va){
            cur = i;
            continue;
        }
        if(P[i].vb - P[i-1].vb == 1){
            c(i-1, i);
        }
    }
    for(int i = 0; i < n; i++){
        ll V = ll(P[i].va-1) << 32 | P[i].vb;
        if(S.count(V)){
            G[f(S[V])].push_back(f(i));
            G[f(i)].push_back(f(S[V]));
        }
    }
    /*
    for(int i = 0; i < n; i++){
        printf("(%d,%d) : %d\n",P[i].va,P[i].vb,f(i));
    }
    */
    for(int i = 0; i < n; i++){
        if(i != f(i)) continue;
        sort(all(G[i]));
        G[i].resize(unique(all(G[i])) - G[i].begin());
        //printf("%d, sz = %d: ",i,sz[i]); for(int u : G[i]) printf("%d ",u); puts("");
    }
    dfsi(f(0));
    dfs(f(0));
    return dis;
}

int DistanceSum(int N, int *X, int *Y){
    n = N;
    for(int i = 0; i < N; i++) P[i] = {X[i],Y[i]};
    ll d1 = pro();
    for(int i = 0; i < N; i++) P[i] = {Y[i],X[i]};
    ll d2 = pro();
    return (d1 + d2) % mod;
}
/*
int main(){
    fio;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> P[i].va >> P[i].vb;
    ll d1 = pro();
    for(int i = 0; i < n; i++) swap(P[i].va, P[i].vb);
    ll d2 = pro();
    cout << (d1 + d2) % mod << '\n';
}
*/

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