# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
134657 | 2019-07-23T06:38:43 Z | sealnot123 | Ideal city (IOI12_city) | C++14 | 123 ms | 12644 KB |
#include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() using namespace std; typedef long long LL; typedef pair<LL,LL> PLL; typedef pair<int,int> PII; typedef double D; typedef long double LD; const int N = 100005; const LL mod = 1000000000; vector<int> compx, compy; int lastx[N], lasty[N]; int orderx[N], ordery[N]; vector<int> g[N]; LL ans; LL dp[N], sz[N]; int n; int *XX, *YY; int cnt, mk[N]; void add_edge(int a, int b){ g[a].pb(b); g[b].pb(a); } bool cmpx(int a, int b){ if(XX[a] != XX[b]) return XX[a] < XX[b]; return YY[a] < YY[b]; } bool cmpy(int a, int b){ if(YY[a] != YY[b]) return YY[a] < YY[b]; return XX[a] < XX[b]; } void dfs(int u, int v){ /* printf("%d\n",u);*/ for(int e : g[u]){ if(e == v) continue; dfs(e, u); ans += (dp[e]+sz[e])*sz[u] + dp[u]*sz[e]; dp[u] += dp[e] + sz[e]; sz[u] += sz[e]; } } int DistanceSum(int nn, int *X, int *Y) { n = nn; XX = X; YY = Y; int i,j,k,l,a,b,c,d; for(i=0;i<n;i++) compx.pb(X[i]), compy.pb(Y[i]); sort(all(compx)); sort(all(compy)); compx.erase(unique(all(compx)), compx.end()); compy.erase(unique(all(compy)), compy.end()); for(i=0;i<n;i++) orderx[i] = ordery[i] = i; sort(orderx,orderx+n,cmpx); sort(ordery,ordery+n,cmpy); memset(lastx, -1, sizeof lastx); memset(lasty, -1, sizeof lasty); for(i = 0; i < n; i++){ /*printf("#%d %d :",X[orderx[i]],Y[orderx[i]]);*/ if(i == 0 || X[orderx[i]] == X[orderx[i-1]] && Y[orderx[i]] == Y[orderx[i-1]]+1); else cnt++; mk[orderx[i]] = cnt; sz[cnt]++; /*printf("%d\n",cnt);*/ } for(i = 0; i < n; i++){ b = orderx[i]; /* printf("%d ",b);*/ a = lower_bound(all(compy), Y[b]) - compy.begin(); if(lasty[a] != -1 && X[lasty[a]] + 1 == X[b]){ add_edge(mk[lasty[a]], mk[b]); /*printf("x %d %d\n",mk[lasty[a]],mk[b]);*/ } lasty[a] = orderx[i]; } /* printf("\n");*/ for(i=0;i<n;i++){ sort(all(g[i])); g[i].erase(unique(all(g[i])), g[i].end()); } dfs(0,0); for(i=0;i<n;i++) g[i].clear(); memset(dp, 0, sizeof dp); memset(sz, 0, sizeof sz); cnt = 0; for(i = 0; i < n; i++){ /*printf("#%d %d :",X[ordery[i]],Y[ordery[i]]);*/ if(i == 0 || Y[ordery[i]] == Y[ordery[i-1]] && X[ordery[i]] == X[ordery[i-1]]+1); else cnt++; mk[ordery[i]] = cnt; sz[cnt]++; /*printf("%d\n",cnt);*/ } for(i = 0; i < n; i++){ b = ordery[i]; /* printf("%d ",b);*/ a = lower_bound(all(compx), X[b]) - compx.begin(); if(lastx[a] != -1 && Y[lastx[a]] + 1 == Y[b]){ add_edge(mk[lastx[a]], mk[b]); /*printf("y %d %d\n",mk[lastx[a]],mk[b]);*/ } lastx[a] = ordery[i]; } for(i=0;i<n;i++){ sort(all(g[i])); g[i].erase(unique(all(g[i])), g[i].end()); } /* printf("\n");*/ dfs(0,0); return ans%mod; } /* 4 0 0 0 1 0 2 0 3 (10) 4 1 1 1 2 2 1 2 2 11 3 3 3 4 3 5 4 4 4 5 5 2 5 4 6 2 6 3 6 4 6 5 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5112 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4956 KB | Output is correct |
4 | Correct | 7 ms | 4984 KB | Output is correct |
5 | Correct | 7 ms | 5108 KB | Output is correct |
6 | Correct | 8 ms | 4984 KB | Output is correct |
7 | Correct | 7 ms | 4984 KB | Output is correct |
8 | Correct | 6 ms | 4984 KB | Output is correct |
9 | Correct | 6 ms | 5112 KB | Output is correct |
10 | Correct | 6 ms | 4984 KB | Output is correct |
11 | Correct | 6 ms | 5112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 5112 KB | Output is correct |
2 | Correct | 7 ms | 5112 KB | Output is correct |
3 | Correct | 8 ms | 5240 KB | Output is correct |
4 | Correct | 8 ms | 5084 KB | Output is correct |
5 | Correct | 9 ms | 5112 KB | Output is correct |
6 | Correct | 8 ms | 5112 KB | Output is correct |
7 | Correct | 8 ms | 5112 KB | Output is correct |
8 | Correct | 7 ms | 5112 KB | Output is correct |
9 | Correct | 7 ms | 5112 KB | Output is correct |
10 | Correct | 8 ms | 5112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 6008 KB | Output is correct |
2 | Correct | 23 ms | 6392 KB | Output is correct |
3 | Correct | 53 ms | 7504 KB | Output is correct |
4 | Correct | 53 ms | 7924 KB | Output is correct |
5 | Correct | 104 ms | 9964 KB | Output is correct |
6 | Correct | 114 ms | 10928 KB | Output is correct |
7 | Correct | 115 ms | 10732 KB | Output is correct |
8 | Correct | 109 ms | 9800 KB | Output is correct |
9 | Correct | 114 ms | 10476 KB | Output is correct |
10 | Correct | 116 ms | 12644 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 6136 KB | Output is correct |
2 | Correct | 28 ms | 6264 KB | Output is correct |
3 | Correct | 60 ms | 7692 KB | Output is correct |
4 | Correct | 60 ms | 7896 KB | Output is correct |
5 | Correct | 123 ms | 10448 KB | Output is correct |
6 | Correct | 117 ms | 10576 KB | Output is correct |
7 | Correct | 123 ms | 10476 KB | Output is correct |
8 | Correct | 120 ms | 10476 KB | Output is correct |
9 | Correct | 116 ms | 10220 KB | Output is correct |
10 | Correct | 116 ms | 10348 KB | Output is correct |