Submission #868399

#	Time	Username	Problem	Language	Result	Execution time	Memory
868399		abcvuitunggio	Ideal city (IOI12_city)	C++17	100 / 100	265 ms	15868 KiB

city

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9;
int p[100000],sz[100000],n,res,vis[100000];
vector <int> ke[100000];
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
    i=f(i);
    j=f(j);
    if (i==j)
        return;
    if (sz[i]<sz[j])
        swap(i,j);
    sz[i]+=sz[j];
    p[j]=i;
}
void dfs(int u, int p){
    vis[u]=1;
    for (int v:ke[u])
        if (!vis[v]&&v!=p){
            dfs(v,u);
            sz[u]+=sz[v];
        }
    res=(res+1LL*sz[u]*(n-sz[u])%mod)%mod;
}
int calc(int *x, int *y){
    map <pair <int, int>, int> mp;
    for (int i=0;i<n;i++){
        mp[{x[i],y[i]}]=i;
        p[i]=i;
        sz[i]=1;
        vis[i]=0;
        ke[i].clear();
    }
    for (int i=0;i<n;i++)
        if (mp.count({x[i]-1,y[i]}))
            unite(mp[{x[i]-1,y[i]}],i);
    for (int i=0;i<n;i++)
        if (mp.count({x[i],y[i]-1})){
            int j=f(mp[{x[i],y[i]-1}]);
            ke[f(i)].push_back(j);
            ke[j].push_back(f(i));
        }
    res=0;
    dfs(f(0),-1);
    return res;
}
int DistanceSum(int N, int *X, int *Y){
    n=N;
    return (calc(X,Y)+calc(Y,X))%mod;
}

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