제출 #436498

#제출 시각아이디문제언어결과실행 시간메모리
436498dacin21분수 공원 (IOI21_parks)C++17
45 / 100
1031 ms62520 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; const int U = 1.01e5; struct Segment{ int x, y; bool vert; }; struct Range{ int a, b; }; struct Dsu{ Dsu(int n_) : p(n_, -1){} int f(int x){ return p[x] < 0 ? x : p[x] = f(p[x]); } bool u(int a, int b){ a = f(a); b = f(b); if(a == b) return false; p[b] = a; return true; } vector<int> p; }; // 2-sat in linear time via backtracking. class Two_Sat { public: int N; // number of variables vector<int> val; // assignment of x is at val[2x] and -x at val[2x+1] vector<char> valid; // changes made at time i are kept iff valid[i] vector<vector<int> > G; // graph of implications G[x][i] = y means (x -> y) Two_Sat(int N_) : N(N_) { // create a formula over N variables (numbered 1 to N) G.resize(2*N); } int add_variable() { G.emplace_back(); G.emplace_back(); return N++; } private: // converts a signed variable index to its position in val[] and G[] int to_ind(int x) { return 2*(abs(x)-1) + (x<0); } // Add a directed edge to the graph. // You most likely do not want to call this yourself! void add_edge(int a, int b) { G[to_ind(a)].push_back(to_ind(b)); } int time() { return valid.size()-1; } bool dfs(int x) { if(valid[abs(val[x])]) return val[x]>0; val[x] = time(); val[x^1] = -time(); for(int e:G[x]) if(!dfs(e)) return false; return true; } public: // Add the or-clause: (a or b) void add_or(int a, int b) { add_edge(-a,b); add_edge(-b,a); } // Add the implication: a -> b void add_implication(int a, int b) { add_or(-a, b); } // Add condition: x is true void add_true(int x) { add_or(x,x); } // At most one with linear number of clauses template<typename T> void add_at_most_one(T vars) { if(vars.begin() == vars.end()) return; int last = *vars.begin(); int cur = 0; for(int const&e:vars){ if(e == last) continue; if(cur == 0) cur = e; else { add_or(-cur, -e); int new_cur = add_variable(); cur = add_implication(cur, new_cur); add_implication(e, new_cur); cur = new_cur; } } if(cur != 0){ add_or(-cur, -last); } } bool solve() { val.assign(2*N, 0); valid.assign(1, 0); for(int i=0; i<(int)val.size(); i+=2) { if(!valid[abs(val[i])]) { valid.push_back(1); if(!dfs(i)) { valid.back()=0; valid.push_back(1); if(!dfs(i+1)) return false; } } } return true; } }; int construct_roads(vector<int> X, vector<int> Y) { const int n = X.size(); map<pair<int, int>, int> decode; for(int i=0; i<n; ++i){ decode[make_pair(X[i], Y[i])] = i; } vector<array<int, 4> > to(n, {-1, -1, -1, -1}); vector<array<int, 4> > var(n, {0, 0, 0, 0}); int vars = 0; for(int i=0; i<n; ++i){ for(int j=0; j<4; ++j){ int x = X[i], y = Y[i]; if(j == 0) x+=2; if(j == 2) x-=2; if(j == 1) y+=2; if(j == 3) y-=2; if(decode.count(make_pair(x, y))){ to[i][j] = decode[make_pair(x, y)]; if(var[i][j] == 0){ ++vars; var[i][j] = vars; var[to[i][j]][j^2] = vars; } //cerr << i << " " << X[i] << " " << Y[i] << " with " << j << " -> " << x << " " << y << " " << to[i][j] << " " << var[i][j] << "\n"; } } } Two_Sat sat(vars); auto check = [&](int a, int b){ if(a == 0 || b == 0) return; //cerr << "or " << a << " " << b << "\n"; sat.add_or(a, b); }; for(int i=0; i<n; ++i){ check(var[i][0], var[i][1]); check(var[i][2], -var[i][1]); check(-var[i][2], -var[i][3]); check(-var[i][0], var[i][3]); } assert(sat.solve()); Dsu uni(n); vector<int> out_a, out_b, out_x, out_y; for(int i=0; i<n; ++i){ for(int j=0; j<4; ++j) if(to[i][j] != -1){ const int e = to[i][j]; if(uni.u(i, e)){ out_a.push_back(i); out_b.push_back(e); int x = X[i]; int y = Y[i]; if(j == 0) x+=1; if(j == 2) x-=1; if(j == 1) y+=1; if(j == 3) y-=1; int add; if(sat.val[2*var[i][j]-2]>0){ add = -1; } else { add = 1; } if(j%2 == 0) y += add; else x += add; out_x.push_back(x); out_y.push_back(y); } } } if((int)out_x.size() == n-1){ build(out_a, out_b, out_x, out_y); return 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...