제출 #63391

#제출 시각아이디문제언어결과실행 시간메모리
63391evpipis이상적인 도시 (IOI12_city)C++11
100 / 100
327 ms22488 KiB
#include <bits/stdc++.h> using namespace std; //#define TEST #define fi first #define se second #define pb push_back #define mp make_pair typedef long long ll; typedef pair<int, int> ii; #ifdef TEST #define inbuf_len 1 << 16 #define outbuf_len 1 << 16 #endif // TEST const int len = 1e5+5, mod = 1e9; int par[len], dep[len], cnt[len], val[len], sum[len], n; pair<ii, int> arr[len]; vector<int> adj[len]; set<ii> myset; int add(int a, int b){ return (a+b)%mod; } int sub(int a, int b){ return (mod+a-b)%mod; } int mul(int a, int b){ return (a*1LL*b)%mod; } int fin(int i){ if (par[i] == i) return i; return par[i] = fin(par[i]); } void join(int i, int j){ i = fin(i), j = fin(j); if (i != j) par[i] = j, val[j] += val[i]; } bool comp(pair<ii, int> a, pair<ii, int> b){ if (a.fi.se < b.fi.se) return true; if (a.fi.se > b.fi.se) return false; return (a.fi.fi < b.fi.fi); } int dfs(int u, int p){ //printf("u = %d, p = %d, val = %d\n", u, p, val[u]); cnt[u] = val[u]; sum[u] = mul(val[u], dep[u]); int ans = 0; for (int j = 0; j < adj[u].size(); j++){ int v = adj[u][j]; if (v == p) continue; dep[v] = dep[u]+1; ans = add(ans, dfs(v, u)); cnt[u] = add(cnt[u], cnt[v]); sum[u] = add(sum[u], sum[v]); } //printf("u = %d, cnt = %d, sum = %d\n", u, cnt[u], sum[u]); for (int j = 0; j < adj[u].size(); j++){ int v = adj[u][j]; if (v == p) continue; ans = add(ans, mul(sub(cnt[u], cnt[v]), sub(sum[v], mul(cnt[v], dep[u])))); //ans += (cnt[u]-val[u]-cnt[v]+1) * (sum[v]-cnt[v]*1LL*dep[u]); } //printf("u = %d, ans = %d\n", u, ans); return ans; } int solve(){ //printf("solve starts\n"); myset.clear(); for (int i = 0; i < n; i++){ par[i] = i; val[i] = 1; cnt[i] = 0; adj[i].clear(); } sort(arr, arr+n); for (int i = 0; i < n-1; i++) if (arr[i].fi.fi == arr[i+1].fi.fi && arr[i].fi.se+1 == arr[i+1].fi.se) join(arr[i].se, arr[i+1].se); sort(arr, arr+n, comp); for (int i = 0; i < n-1; i++){ int a = fin(arr[i].se), b = fin(arr[i+1].se); if (arr[i].fi.se == arr[i+1].fi.se && arr[i].fi.fi+1 == arr[i+1].fi.fi && !myset.count(mp(a, b))){ adj[a].pb(b); adj[b].pb(a); myset.insert(mp(a, b)); myset.insert(mp(b, a)); } } int ans = 0; for (int i = 0; i < n; i++) if (cnt[i] == 0 && adj[i].size()) ans = add(ans, dfs(i, i)); return ans; } int DistanceSum(int N, int *X, int *Y){ n = N; for (int i = 0; i < n; i++) arr[i].fi = mp(X[i], Y[i]); for (int i = 0; i < n; i++) arr[i].se = i; int ans = solve(); for (int i = 0; i < n; i++) swap(arr[i].fi.fi, arr[i].fi.se); ans = add(ans, solve()); return ans; } #ifdef TEST int main() { freopen("example.txt", "r", stdin); int tmp; /* Set input and output buffering */ char *inbuf, *outbuf; inbuf = (char*) malloc(inbuf_len * sizeof(char)); outbuf = (char*) malloc(outbuf_len * sizeof(char)); tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len); assert(tmp == 0); tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len); assert(tmp == 0); int N, i; tmp = scanf("%d", &N); assert(tmp == 1); int *sq_x, *sq_y; sq_x = (int*) malloc(N * sizeof(int)); sq_y = (int*) malloc(N * sizeof(int)); for (i = 0; i < N; i++) { tmp = scanf("%d %d", &sq_x[i], &sq_y[i]); assert(tmp == 2); } int ds = DistanceSum(N, sq_x, sq_y); printf("%d\n", ds); return 0; } #endif

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

city.cpp: In function 'int dfs(int, int)':
city.cpp:59:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
city.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...