Submission #30626

# Submission time Handle Problem Language Result Execution time Memory
30626 2017-07-25T14:45:31 Z top34051 Ideal city (IOI12_city) C++14
0 / 100
56 ms 8416 KB
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define mod 1000000007LL
int head[maxn];
long long 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;
    ans = (ans + now*val[x]);
    for(i=0;i<from[x].size();i++) {
        if(!vis[from[x][i]]) {
            now = (now + sum[x] - sum[from[x][i]] - sum[from[x][i]] + mod)%mod;
            dfs2(from[x][i]);
            now = (now - sum[x] + 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;
    memset(vis,0,sizeof(vis));
    dfs(x,0);
    memset(vis,0,sizeof(vis));
    dfs2(x);
}
int DistanceSum(int N,int* X,int* Y) {
    ans = 0;
    solve(N,X,Y,0);
    solve(N,X,Y,1);
    return ans/2;
}

Compilation message

city.cpp: In function 'void dfs(int, int)':
city.cpp:14: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:26: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:63:12: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs2(x);
            ^
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 6556 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6688 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 8416 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 8416 KB Output isn't correct
2 Halted 0 ms 0 KB -