제출 #296217

#제출 시각아이디문제언어결과실행 시간메모리
296217alexandra_udristoiu이상적인 도시 (IOI12_city)C++14
100 / 100
60 ms9208 KiB
#include<iostream> #include<algorithm> #include<vector> #define x first #define y second #define DIM 100005 #define mod 1000000000 using namespace std; static int n, sol, d[DIM], num[DIM]; static pair<int, int> p[DIM]; static vector<int> v[DIM]; struct str{ int pos, p, u; }; str w[DIM]; void dfs(int nod, int t){ d[nod] = 0; num[nod] = w[nod].u - w[nod].p + 1; for(int i = 0; i < v[nod].size(); i++){ int vecin = v[nod][i]; if(vecin == t){ continue; } dfs(vecin, nod); sol = (sol + num[nod] * 1LL * (d[vecin] + num[vecin]) ) % mod; sol = (sol + num[vecin] * 1LL * d[nod]) % mod; d[nod] += d[vecin] + num[vecin]; num[nod] += num[vecin]; } } void solve(){ int i, j, nr = 0; sort(p + 1, p + n + 1); for(i = 1; i <= n; i++){ nr++; w[nr].pos = p[i].x; w[nr].p = p[i].y; for(j = i + 1; j <= n; j++){ if(p[j].x != p[i].x || p[j].y != p[j - 1].y + 1){ break; } } j--; w[nr].u = p[j].y; i = j; } j = 1; for(i = 1; i <= nr; i++){ while(j < i && w[j].pos + 1 < w[i].pos || (w[j].pos + 1 == w[i].pos && w[j].u < w[i].p) ){ j++; } while(j < i && w[j].pos + 1 == w[i].pos && max(w[i].p, w[j].p) <= min(w[i].u, w[j].u) ){ v[i].push_back(j); v[j].push_back(i); j++; } j--; } dfs(1, 0); } int DistanceSum(int N, int *X, int *Y) { int i; n = N; for(i = 1; i <= n; i++){ p[i] = make_pair(X[i - 1], Y[i - 1]); } solve(); for(i = 1; i <= n; i++){ v[i].clear(); } for(i = 1; i <= n; i++){ p[i] = make_pair(Y[i - 1], X[i - 1]); } solve(); return sol; }

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

city.cpp: In function 'void dfs(int, int)':
city.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
city.cpp: In function 'void solve()':
city.cpp:49:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   49 |         while(j < i && w[j].pos + 1 < w[i].pos || (w[j].pos + 1 == w[i].pos && w[j].u < w[i].p) ){
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...