제출 #134655

#제출 시각아이디문제언어결과실행 시간메모리
134655sealnot123이상적인 도시 (IOI12_city)C++14
32 / 100
26 ms6244 KiB
#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; 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; } /* 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 */

컴파일 시 표준 에러 (stderr) 메시지

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:69:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(i == 0 || X[orderx[i]] == X[orderx[i-1]] && Y[orderx[i]] == Y[orderx[i-1]]+1);
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:97:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(i == 0 || Y[ordery[i]] == Y[ordery[i-1]] && X[ordery[i]] == X[ordery[i-1]]+1);
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:56:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
        ^
city.cpp:56:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
          ^
city.cpp:56:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
            ^
city.cpp:56:18: warning: unused variable 'c' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                  ^
city.cpp:56:20: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...