Submission #1124380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124380		tosivanmak	Ideal city (IOI12_city)	C++20	100 / 100	325 ms	29492 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1000000000;


bool vis[100005];
vector<ll>adj[100005];
map<pair<ll,ll>,bool>mp;
map<pair<ll,ll>,bool>exist;
map<pair<ll,ll>,ll>assigned;
ll nodesize[100005], subsize[100005], dist[100005];
vector<pair<ll,ll> > nds;
ll totdist=0,ans=0;

void dfs(ll s){
    vis[s]=1;
    subsize[s]=nodesize[s];
    for(auto& u: adj[s]){
        if(!vis[u]){
            dist[u]=dist[s]+1;
            dfs(u);
            subsize[s]+=subsize[u];
        }
    }
}
void compute(ll s){
    vis[s]=1;
    ans+=nodesize[s]*totdist;
    for(auto& u: adj[s]){
        if(!vis[u]){
            totdist+=(subsize[1]-subsize[u]);
            totdist-=subsize[u];
            compute(u);
            totdist-=(subsize[1]-subsize[u]);
            totdist+=subsize[u];
        }
    }
}
void clear(){
    for(int i=1;i<=100000;i++){
        vis[i]=0; adj[i].clear(); nodesize[i]=0; subsize[i]=0; dist[i]=0;
    }
    mp.clear(); exist.clear(); assigned.clear(); nds.clear();
    totdist=0;
}
int DistanceSum(int N, int *X, int *Y){
    for(int i=0;i<N;i++){
        mp[{X[i],Y[i]}]=1;
        nds.push_back({X[i],Y[i]});
    }
    ll assign=1;
    sort(nds.begin(),nds.end());
    for(int i=0;i<nds.size();i++){
        if(i==0) assigned[nds[i]]=assign, nodesize[assign]++;
        else{
            if(nds[i].first==nds[i-1].first&&nds[i].second==nds[i-1].second+1){
                assigned[nds[i]]=assign; nodesize[assign]++;
            }
            else{
                assigned[nds[i]]=assign+1; nodesize[assign+1]++; assign++;
            }
        }
    }
    for(int i=0;i<nds.size();i++){
        if(mp[{nds[i].first+1,nds[i].second}]){
            if(!exist[{assigned[nds[i]],assigned[{nds[i].first+1,nds[i].second}]}]){
                ll u=assigned[nds[i]]; ll v=assigned[{nds[i].first+1,nds[i].second}];
                adj[u].push_back(v); adj[v].push_back(u);
                exist[{u,v}]=exist[{v,u}]=1;
            }
        }
    }
    dist[1]=0;
    dfs(1);
    for(int i=1;i<=100000;i++) vis[i]=0;
    for(int i=1;i<=assign;i++){
        totdist+=nodesize[i]*dist[i];
    }
    compute(1);
    clear();
    for(int i=0;i<N;i++){
        mp[{Y[i],X[i]}]=1;
        nds.push_back({Y[i],X[i]});
    }
    assign=1;
    sort(nds.begin(),nds.end());
    for(int i=0;i<nds.size();i++){
        if(i==0) assigned[nds[i]]=assign, nodesize[assign]++;
        else{
            if(nds[i].first==nds[i-1].first&&nds[i].second==nds[i-1].second+1){
                assigned[nds[i]]=assign; nodesize[assign]++;
            }
            else{
                assigned[nds[i]]=assign+1; nodesize[assign+1]++; assign++;
            }
        }
    }
    for(int i=0;i<nds.size();i++){
        if(mp[{nds[i].first+1,nds[i].second}]){
            if(!exist[{assigned[nds[i]],assigned[{nds[i].first+1,nds[i].second}]}]){
                ll u=assigned[nds[i]]; ll v=assigned[{nds[i].first+1,nds[i].second}];
                adj[u].push_back(v); adj[v].push_back(u);
                exist[{u,v}]=exist[{v,u}]=1;
            }
        }
    }
    dfs(1);
    for(int i=1;i<=100000;i++) vis[i]=0;
    for(int i=1;i<=assign;i++){
        totdist+=nodesize[i]*dist[i];
    }
    compute(1);
    clear();
    ans/=2;
    return (ans%MOD);
}

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