Submission #30629

#	Time	Username	Problem	Language	Result	Execution time	Memory
30629		top34051	Ideal city (IOI12_city)	C++14	100 / 100	513 ms	17332 KiB

city

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define mod 10000000000LL
#define mod2 1000000000LL
int head[maxn];
long long all, now, ans;
long long sum[maxn], val[maxn];
bool vis[maxn];
vector<int> from[maxn];
map<pair<int,int>, int> p;
void dfs(int x,int h) {
    int i;
    vis[x] = 1; now = (now + val[x]*h)%mod;
    for(i=0;i<from[x].size();i++) {
        if(!vis[from[x][i]]) {
            dfs(from[x][i],h+1);
            sum[x] = (sum[x] + sum[from[x][i]])%mod;
        }
    }
    sum[x] = (sum[x] + val[x])%mod;
}
void dfs2(int x) {
    int i;
    vis[x] = 1;
//    printf("dfs2 %d : now = %lld  =>  %lld\n",x,now,now*val[x]);
    ans = (ans + now*val[x]);
    for(i=0;i<from[x].size();i++) {
        if(!vis[from[x][i]]) {
            now = (now + all - sum[from[x][i]] - sum[from[x][i]] + mod)%mod;
            dfs2(from[x][i]);
            now = (now - all + sum[from[x][i]] + sum[from[x][i]] + mod)%mod;
        }
    }
}
int findhead(int x) {
    if(head[x]==x) return x;
    return head[x] = findhead(head[x]);
}
void solve(int N, int *X, int *Y,int type) {
    int i,x;
    pair<int,int> t;
    map<pair<int,int>, int>::iterator it;
    p.clear();
    memset(sum,0,sizeof(sum)); memset(val,0,sizeof(val));
    for(i=0;i<N;i++) head[i] = i, from[i].clear();
    for(i=0;i<N;i++) {
        if(type==0) p[{X[i],Y[i]}] = i;
        else p[{Y[i],X[i]}] = i;
    }
    for(it=p.begin();it!=p.end();++it) {
        t = it->first;
        if(p.find({t.first,t.second+1})!=p.end()) head[findhead(p[t])] = findhead(p[{t.first,t.second+1}]);
    }
    for(i=0;i<N;i++) val[findhead(i)]++;
    for(it=p.begin();it!=p.end();++it) {
        t = it->first;
        if(p.find({t.first+1,t.second})!=p.end()) from[findhead(p[t])].push_back(findhead(p[{t.first+1,t.second}]));
        if(p.find({t.first-1,t.second})!=p.end()) from[findhead(p[t])].push_back(findhead(p[{t.first-1,t.second}]));
    }
    for(i=0;i<N;i++) if(val[i]) x = i;
    all = N; now = 0;
    memset(vis,0,sizeof(vis));
    dfs(x,0);
    memset(vis,0,sizeof(vis));
    dfs2(x);
//    printf("ans = %lld\n",ans);
}
int DistanceSum(int N,int* X,int* Y) {
    ans = 0;
    solve(N,X,Y,0);
    solve(N,X,Y,1);
    return (ans/2+mod2)%mod2;
}

Compilation message (stderr)

city.cpp: In function 'void dfs(int, int)':
city.cpp:15:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<from[x].size();i++) {
              ^
city.cpp: In function 'void dfs2(int)':
city.cpp:28:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<from[x].size();i++) {
              ^
city.cpp: In function 'void solve(int, int*, int*, int)':
city.cpp:66:12: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs2(x);
            ^

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