제출 #436227

#제출 시각아이디문제언어결과실행 시간메모리
436227CodePlatina분수 공원 (IOI21_parks)C++17
55 / 100
3582 ms93896 KiB
#include "parks.h" #include <iostream> #include <vector> #include <algorithm> #include <tuple> #include <random> #include <chrono> #define pii pair<int, int> #define ff first #define ss second using namespace std; const int INF = 202020; vector<pii> lsX[INF]; vector<pii> lsY[INF]; vector<pii> eg, tr; int par[202020]; int fnd(int x) { return x == par[x] ? x : par[x] = fnd(par[x]); } void uni(int x, int y) { par[fnd(x)] = fnd(y); } vector<int> U, V, A, B; vector<int> gph[404040]; int ord[404040]; int scc[404040]; int scnt = 0, cnt = 0; vector<int> S; int dfs(int x, int p) { int ret = ord[x] = ++cnt; S.push_back(x); for(int y : gph[x]) if(y != p) { if(!ord[y]) ret = min(ret, dfs(y, x)); else if(!scc[y]) ret = min(ret, ord[y]); } if(ret >= ord[x]) { ++scnt; while(S.back() != x) scc[S.back()] = scnt, S.pop_back(); scc[S.back()] = scnt, S.pop_back(); } return ret; } int construct_roads(vector<int> x, vector<int> y) { int n = x.size(); for(int i = 0; i < n; ++i) lsX[x[i]].push_back({y[i], i}); for(int i = 0; i < n; ++i) lsY[y[i]].push_back({x[i], i}); for(int i = 0; i < INF; ++i) { sort(lsX[i].begin(), lsX[i].end()); for(int j = 0; j < (int)lsX[i].size() - 1; ++j) if(lsX[i][j + 1].ff - lsX[i][j].ff == 2) eg.push_back({lsX[i][j].ss, lsX[i][j + 1].ss}); } for(int i = 0; i < INF; ++i) { sort(lsY[i].begin(), lsY[i].end()); for(int j = 0; j < (int)lsY[i].size() - 1; ++j) if(lsY[i][j + 1].ff - lsY[i][j].ff == 2) eg.push_back({lsY[i][j].ss, lsY[i][j + 1].ss}); } unsigned seed = chrono::steady_clock::now().time_since_epoch().count(); mt19937 rng(seed); for(int cs = 0; cs < 30; ++cs) { shuffle(eg.begin(), eg.end(), rng); for(int i = 0; i < 202020; ++i) par[i] = i; tr.clear(); for(auto i : eg) if(fnd(i.ff) != fnd(i.ss)) tr.push_back(i), uni(i.ff, i.ss); if(tr.size() != n - 1) return 0; pii C[n - 1], D[n - 1]; vector<pii> pr; int c = 0; for(auto [i, j] : tr) { if(x[i] == x[j]) { C[c] = {x[i] - 1, y[i] + 1}; D[c] = {x[i] + 1, y[i] + 1}; } else { C[c] = {x[i] + 1, y[i] - 1}; D[c] = {x[i] + 1, y[i] + 1}; } pr.push_back(C[c]); pr.push_back(D[c]); ++c; } sort(pr.begin(), pr.end()); pr.resize(unique(pr.begin(), pr.end()) - pr.begin()); int E[n - 1], F[n - 1]; for(int i = 0; i < n - 1; ++i) E[i] = lower_bound(pr.begin(), pr.end(), C[i]) - pr.begin(); for(int i = 0; i < n - 1; ++i) F[i] = lower_bound(pr.begin(), pr.end(), D[i]) - pr.begin(); int N = pr.size(); vector<pii> ls[N]; for(int i = 0; i < n - 1; ++i) ls[E[i]].push_back({i, 0}); for(int i = 0; i < n - 1; ++i) ls[F[i]].push_back({i, 1}); cnt = scnt = 0; for(int i = 0; i < 2 * n; ++i) gph[i].clear(), ord[i] = scc[i] = 0; S.clear(); for(int i = 0; i < N; ++i) { int sz = ls[i].size(); for(int j = 0; j < sz; ++j) { for(int k = 0; k < sz; ++k) { if(j != k) { int p = ls[i][j].ff + ls[i][j].ss * n; int q = ls[i][k].ff + (!ls[i][k].ss) * n; gph[p].push_back(q); } } } } for(int i = 0; i < 2 * n; ++i) if(!ord[i]) dfs(i, -1); bool flag = true; for(int i = 0; i < n - 1; ++i) if(scc[i] == scc[i + n]) flag = false; if(!flag) continue; for(int i = 0; i < n - 1; ++i) { U.push_back(tr[i].ff); V.push_back(tr[i].ss); if(scc[i] < scc[i + n]) { A.push_back(C[i].ff); B.push_back(C[i].ss); } else { A.push_back(D[i].ff); B.push_back(D[i].ss); } } build(U, V, A, B); return 1; } return 0; }

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

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:75:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         if(tr.size() != n - 1) return 0;
      |            ~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...