oj.uz

Submission #30629

# Submission time Handle Problem Language Result Execution time Memory
30629 2017-07-25T15:06:04 Z top34051 Ideal city (IOI12_city) C++14
100 / 100
 513 ms 17332 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6556 KB Output is correct
2 Correct 0 ms 6556 KB Output is correct
3 Correct 3 ms 6556 KB Output is correct
4 Correct 0 ms 6556 KB Output is correct
5 Correct 3 ms 6556 KB Output is correct
6 Correct 0 ms 6556 KB Output is correct
7 Correct 0 ms 6556 KB Output is correct
8 Correct 0 ms 6556 KB Output is correct
9 Correct 3 ms 6556 KB Output is correct
10 Correct 0 ms 6556 KB Output is correct
11 Correct 3 ms 6556 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6688 KB Output is correct
2 Correct 6 ms 6688 KB Output is correct
3 Correct 6 ms 6688 KB Output is correct
4 Correct 3 ms 6688 KB Output is correct
5 Correct 6 ms 6688 KB Output is correct
6 Correct 3 ms 6688 KB Output is correct
7 Correct 6 ms 6688 KB Output is correct
8 Correct 9 ms 6688 KB Output is correct
9 Correct 0 ms 6688 KB Output is correct
10 Correct 6 ms 6688 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8416 KB Output is correct
2 Correct 73 ms 8416 KB Output is correct
3 Correct 199 ms 11172 KB Output is correct
4 Correct 219 ms 11052 KB Output is correct
5 Correct 506 ms 15920 KB Output is correct
6 Correct 299 ms 15996 KB Output is correct
7 Correct 423 ms 15788 KB Output is correct
8 Correct 386 ms 16184 KB Output is correct
9 Correct 483 ms 15516 KB Output is correct
10 Correct 429 ms 17332 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8416 KB Output is correct
2 Correct 69 ms 8416 KB Output is correct
3 Correct 193 ms 11304 KB Output is correct
4 Correct 189 ms 11216 KB Output is correct
5 Correct 503 ms 15920 KB Output is correct
6 Correct 496 ms 15904 KB Output is correct
7 Correct 476 ms 16020 KB Output is correct
8 Correct 483 ms 15692 KB Output is correct
9 Correct 506 ms 15656 KB Output is correct
10 Correct 513 ms 15788 KB Output is correct