Submission #227034

#TimeUsernameProblemLanguageResultExecution timeMemory
227034abekerMatching (COCI20_matching)C++17
0 / 110
224 ms524292 KiB
#include <bits/stdc++.h> using namespace std; typedef pair <int, int> pii; const int MAXN = 1e5 + 5; const int offset = 1 << 17; const int MAXV = 1.15e7 + 5; int n; bool sol[MAXV]; bool bio[MAXV]; int comp[MAXV]; vector <int> adj[MAXV], rev[MAXV]; stack <int> order; inline int add_variables(int vars) { n += vars; return n - vars; } void add_edge(int u, int v) { adj[u].push_back(v); rev[v].push_back(u); } void add_implication(int u1, int neg1, int u2, int neg2) { add_edge(2 * u1 + neg1, 2 * u2 + neg2); add_edge(2 * u2 + !neg2, 2 * u1 + !neg1); } void dfs_forward(int x) { bio[x] = true; for (auto it : adj[x]) if (!bio[it]) dfs_forward(it); order.push(x); } void dfs_backward(int x, int c) { comp[x] = c; for (auto it : rev[x]) if (!comp[it]) dfs_backward(it, c); } bool two_sat() { for (int i = 0; i < 2 * n; i++) if (!bio[i]) dfs_forward(i); int ptr = 0; for (; !order.empty(); order.pop()) if (!comp[order.top()]) dfs_backward(order.top(), ++ptr); for (int i = 0; i < 2 * n; i++) { if (comp[i] == comp[i ^ 1]) return false; sol[i] = comp[i] > comp[i ^ 1]; } return true; } int N; int x[MAXN], y[MAXN]; vector <pii> tour[2 * offset]; int st[2 * offset], off[2 * offset]; vector <int> hor[MAXN], ver[MAXN]; unordered_map <int, pii> segs; vector <int> graph[MAXN]; void load() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d%d", x + i, y + i); hor[y[i]].push_back(i); ver[x[i]].push_back(i); } } void insert(int x, int lo, int hi, int from, int to, int var, int height) { if (lo >= to || hi <= from) return; if (lo >= from && hi <= to) { tour[x].push_back({height, var}); return; } int mid = (lo + hi) / 2; insert(2 * x, lo, mid, from, to, var, height); insert(2 * x + 1, mid, hi, from, to, var, height); } inline int get_id(int node, int x) { return x < off[node] ? st[node] + x : tour[node][x - off[node]].second; } void add_clause(int x, int u, int v) { if (u < off[x] + tour[x].size()) add_implication(get_id(x, u), 0, get_id(x, v), 0); } void init(int x) { if (tour[x].empty()) return; off[x] = 1; sort(tour[x].begin(), tour[x].end()); while (off[x] < tour[x].size()) off[x] *= 2; st[x] = add_variables(2 * off[x]); for (int i = 0; i < off[x]; i++) { add_clause(x, 2 * i, i); add_clause(x, 2 * i + 1, i); } } int get_bounds(int x, int val) { int lo = 0, hi = tour[x].size(); while (lo < hi) { int mid = (lo + hi) / 2; if (tour[x][mid].first >= val) hi = mid; else lo = mid + 1; } return lo; } void update(int node, int from, int to, int var) { from += off[node]; to += off[node]; while (from < to) { if (from % 2) add_implication(get_id(node, from++), 0, var, 1); if (to % 2) add_implication(get_id(node, --to), 0, var, 1); from /= 2; to /= 2; } } void add_intersections(int x, int down, int up, int var) { for (x += offset; x; x /= 2) if (off[x]) update(x, get_bounds(x, down), get_bounds(x, up + 1), var); } void bye() { puts("NE"); exit(0); } void solve() { for (int i = 1; i < MAXN; i++) if (hor[i].size() == 2) { int tmp = add_variables(1); segs[tmp] = {hor[i][0], hor[i][1]}; int l = MAXN, r = 0; for (auto it : hor[i]) { graph[it].push_back(tmp); l = min(l, x[it]); r = max(r, x[it]); } insert(1, 0, offset, l, r + 1, tmp, i); } for (int i = 0; i < 2 * offset; i++) init(i); for (int i = 1; i < MAXN; i++) if (ver[i].size() == 2) { int tmp = add_variables(1); segs[tmp] = {ver[i][0], ver[i][1]}; int l = MAXN, r = 0; for (auto it : ver[i]) { graph[it].push_back(tmp); l = min(l, y[it]); r = max(r, y[it]); } add_intersections(i, l, r, tmp); } for (int i = 0; i < N; i++) if (!graph[i].empty()) add_implication(graph[i][0], 1, graph[i][1 % graph[i].size()], 0); else bye(); if (!two_sat()) bye(); puts("DA"); for (auto it : segs) if (sol[2 * it.first]) printf("%d %d\n", it.second.first + 1, it.second.second + 1); } int main() { double timer = clock(); load(); solve(); fprintf(stderr, "%lf\n", (clock() - timer) / CLOCKS_PER_SEC); return 0; }

Compilation message (stderr)

matching.cpp: In function 'void add_clause(int, int, int)':
matching.cpp:97:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (u < off[x] + tour[x].size())
      ~~^~~~~~~~~~~~~~~~~~~~~~~~~
matching.cpp: In function 'void init(int)':
matching.cpp:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (off[x] < tour[x].size())
         ~~~~~~~^~~~~~~~~~~~~~~~
matching.cpp: In function 'void load()':
matching.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", x + i, y + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...