제출 #38119

#제출 시각아이디문제언어결과실행 시간메모리
38119funcsr이상적인 도시 (IOI12_city)C++14
23 / 100
409 ms33396 KiB
#include <iostream> #include <vector> #include <set> #include <cassert> #include <queue> #include <map> #include <algorithm> #define rep(i, n) for (int i=0; i<(n); i++) #define all(xs) xs.begin(), xs.end() #define pb push_back #define _1 first #define _2 second #define INF 1145141919 #define MOD 1000000000 using namespace std; int DX[4] = {-1, 0, 1, 0}; int DY[4] = {0, -1, 0, 1}; typedef pair<int, int> P; map<P, int> mp; vector<int> G[100000]; int par[100000], ord[100000], low[100000], sz[100000]; int W[100000]; vector<P> bridges, els; void dfs(int x, int p, int r) { par[x] = p; sz[x] = 1; ord[x] = low[x] = r; for (int t : G[x]) if (t != p) { if (ord[t] != -1) { if (ord[x] < ord[t]) els.pb(P(x, t)); low[x] = min(low[x], ord[t]); continue; } dfs(t, x, r+1); sz[x] += sz[t]; low[x] = min(low[x], low[t]); if (ord[x] < low[t]) bridges.pb(P(x, t)); else els.pb(P(x, t)); } } int U[100000], R[100000]; vector<int> G2[100000]; int find(int x) { if (U[x] == x) return x; return U[x] = find(U[x]); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (R[x] < R[y]) swap(x, y); U[y] = x; R[x] += R[y]; } int count(vector<P> seq) { sort(all(seq)); int all = 0, sum = 0, ret = 0, last = seq[0]._1; for (P p : seq) all += p._2; for (P p : seq) { if (last != p._1) { int times = (1LL*sum*(all-sum))%MOD; ret = (ret + 1LL*(p._1-last)*times) % MOD; last = p._1; } sum += p._2; } return ret; } int DistanceSum(int N, int *X, int *Y) { rep(i, N) mp[P(X[i], Y[i])] = i; rep(i, N) { rep(k, 2) { P np = P(X[i]+DX[k], Y[i]+DY[k]); if (mp.find(np) != mp.end()) { int t = mp[np]; G[i].pb(t); G[t].pb(i); } } } rep(i, N) ord[i] = low[i] = -1; dfs(0, -1, 0); rep(i, N) W[i] = 1; int s = 0; for (P p : bridges) { int u = p._1, v = p._2; W[u] += sz[v]; W[v] += N-sz[v]; s = (s + 1LL*sz[v]*(N-sz[v])) % MOD; } rep(i, N) U[i] = i, R[i] = 1; for (P p : els) unite(p._1, p._2); rep(i, N) G2[find(i)].pb(i); rep(c, N) if (G2[c].size() > 1) { assert(G2[c].size() >= 4); vector<P> xs, ys; for (int x : G2[c]) { xs.pb(P(X[x], W[x])); ys.pb(P(Y[x], W[x])); } s = (s+count(xs)) % MOD; s = (s+count(ys)) % MOD; } return s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...