oj.uz

Submission #201263

# Submission time Handle Problem Language Result Execution time Memory
201263 2020-02-10T04:45:33 Z gs14004 Matching (COCI20_matching) C++17
110 / 110
 2114 ms 297096 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 100005;
const int MAXT = 2000005;

struct strongly_connected{
	vector<vector<int>> gph;

	void init(int n){
		gph.resize(n);
	}

	void add_edge(int s, int e){
		gph[s].push_back(e);
	}

	vector<int> val, comp, z, cont;
	int Time, ncomps;
	template<class G, class F> int dfs(int j, G& g, F f) {
		int low = val[j] = ++Time, x; z.push_back(j);
		for(auto e : g[j]) if (comp[e] < 0)
			low = min(low, val[e] ?: dfs(e,g,f));

		if (low == val[j]) {
			do {
				x = z.back(); z.pop_back();
				comp[x] = ncomps;
				cont.push_back(x);
			} while (x != j);
			f(cont); cont.clear();
			ncomps++;
		}
		return val[j] = low;
	}
	template<class G, class F> void scc(G& g, F f) {
		int n = sz(g);
		val.assign(n, 0); comp.assign(n, -1);
		Time = ncomps = 0;
		for(int i=0; i<n; i++) if (comp[i] < 0) dfs(i, g, f);
	}

	int piv;
	void get_scc(int n){
		scc(gph, [&](vector<int> &v){});
		for(int i=0; i<n; i++){
			comp[i] = ncomps - comp[i];
		}
		piv = ncomps; 
	}
}scc;

struct twosat{
	strongly_connected scc;
	int n;
	void init(int _n){ scc.init(2*_n); n = _n; }
	int NOT(int x){ return x >= n ? (x - n) : (x + n); }
	void add_edge(int x, int y){
		if((x >> 31) & 1) x = (~x) + n;
		if((y >> 31) & 1) y = (~y) + n;
		scc.add_edge(x, y), scc.add_edge(NOT(y), NOT(x));
	}
	bool satisfy(vector<int> &res){
		scc.get_scc(2*n);
		for(int i=0; i<n; i++){
			if(scc.comp[i] == scc.comp[NOT(i)]) return 0;
			if(scc.comp[i] < scc.comp[NOT(i)]) res[i] = 0;
			else res[i] = 1;
		}
		return 1;
	}
}twosat;

struct point{
	int x, y, idx;
}a[MAXN];

int n, vis[MAXN], cmp;
vector<int> gph[MAXN];

struct edg{
	int i1, i2, cmp;
};

vector<pi> ev_in[MAXN];
vector<pi> ev_out[MAXN];
vector<edg> cur_insec[MAXN];

struct node{
	int l, r;
}tree[MAXT]; 

int newnode(){ return cmp++; }
int root[MAXN];

void init(int s, int e, int p){
	if(s == e) return;
	tree[p].l = newnode();
	tree[p].r = newnode();
	int m = (s+e)/2;
	init(s, m, tree[p].l);
	init(m+1, e, tree[p].r);
	twosat.add_edge(p, tree[p].l);
	twosat.add_edge(p, tree[p].r);
}

void upd(int pos, int s, int e, int prv, int cur, int val){
	if(s == e){
		if(val != (1 << 30)) twosat.add_edge(cur, val);
		return;
	}
	int m = (s+e)/2;
	if(pos <= m){
		tree[cur].l = newnode();
		tree[cur].r = tree[prv].r;
		upd(pos, s, m, tree[prv].l, tree[cur].l, val);
	}
	else{
		tree[cur].r = newnode();
		tree[cur].l = tree[prv].l;
		upd(pos, m+1, e, tree[prv].r, tree[cur].r, val);
	}
	twosat.add_edge(cur, tree[cur].l);
	twosat.add_edge(cur, tree[cur].r);
}

void query(int s, int e, int ps, int pe, int p, int v){
	if(e < ps || pe < s) return;
	if(s <= ps && pe <= e){
		twosat.add_edge(v, p);
		return;
	}
	int pm = (ps+pe)/2;
	query(s, e, ps, pm, tree[p].l, v);
	query(s, e, pm+1, pe, tree[p].r, v);
}

void Do(vector<edg> &vert, vector<edg> &hori){
	for(auto &i : vert){
		ev_in[a[i.i1].y].emplace_back(a[i.i1].x, i.cmp);
		ev_out[a[i.i2].y + 1].emplace_back(a[i.i1].x, -1);
	}
	for(auto &i : hori){
		cur_insec[a[i.i1].y].push_back(i);
	}
	root[0] = newnode();
	init(1, 100000, root[0]);
	for(int i=1; i<MAXN; i++){
		int prv = root[i - 1];
		for(auto &j : ev_out[i]){
			int nxt = newnode();
			upd(j.first, 1, 100000, prv, nxt, 1 << 30);
			prv = nxt;
		}
		for(auto &j : ev_in[i]){
			int nxt = newnode();
			upd(j.first, 1, 100000, prv, nxt, ~j.second);
			prv = nxt;
		}
		root[i] = prv;
		for(auto &j : cur_insec[i]){
			int s = a[j.i1].x;
			int e = a[j.i2].x;
			query(s, e, 1, 100000, root[i], j.cmp);
		}
	}
}

vector<edg> edges;

void dfs(int x, int p, int q){
	if(vis[x]) return;
	vis[x] = 1;
	for(auto &i : gph[x]){
		if(i != p){
			edges.push_back({i, x, q});
			dfs(i, x, ~q);
			break;
		}
	}
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i].x,&a[i].y);
		a[i].idx = i;
	}
	if(n % 2 == 1){
		puts("NE");
		return 0;
	}
	sort(a, a + n, [&](const point &a, const point &b){
			return pi(a.x, a.y) < pi(b.x, b.y);
			});
	for(int i=1; i<n; i++){
		if(a[i-1].x == a[i].x){
			gph[a[i-1].idx].push_back(a[i].idx);
			gph[a[i].idx].push_back(a[i-1].idx);
		}
	}
	sort(a, a + n, [&](const point &a, const point &b){
			return pi(a.y, a.x) < pi(b.y, b.x);
			});
	for(int i=1; i<n; i++){
		if(a[i-1].y == a[i].y){
			gph[a[i-1].idx].push_back(a[i].idx);
			gph[a[i].idx].push_back(a[i-1].idx);
		}
	}
	sort(a, a + n, [&](const point &a, const point &b){
			return a.idx < b.idx;
			});
	twosat.init(2040000);
	for(int i=0; i<n; i++){
		if(vis[i]) continue;
		if(sz(gph[i]) == 0){
			puts("NE");
			return 0;
		}
		if(sz(gph[i]) == 1){
			int cur_edge = sz(edges);
			dfs(i, -1, cmp);
			int diff_edge = sz(edges) - cur_edge;
			if(diff_edge % 2){
				twosat.add_edge(~cmp, cmp);
			}
			else{
				puts("NE");
				return 0;
			}
			cmp++;
		}
	}
	for(int i=0; i<n; i++){
		if(vis[i]) continue;
		if(sz(gph[i]) == 2){
			if(gph[i][0] == gph[i][1]){
				vis[i] = vis[gph[i][0]] = 1;
				continue;
			}
			dfs(i, -1, cmp);
			cmp++;
		}
	}
	vector<edg> vert, hori;
	for(auto &i : edges){
		if(a[i.i1].x == a[i.i2].x) vert.push_back(i);
		else hori.push_back(i);
	}
	for(auto &i : vert) if(a[i.i1].y > a[i.i2].y) swap(i.i1, i.i2);
	for(auto &i : hori) if(a[i.i1].x > a[i.i2].x) swap(i.i1, i.i2);
	Do(vert, hori);
	vector<int> ans; ans.resize(2040000);
	if(!twosat.satisfy(ans)){
		puts("NE");
		return 0;
	}
	puts("DA");
	int cnt = 0;
	for(auto &i : edges){
		if(i.cmp < 0 && !ans[~i.cmp]) printf("%d %d\n", i.i1 + 1, i.i2 + 1);
		if(i.cmp >= 0 && ans[i.cmp]) printf("%d %d\n", i.i1 + 1, i.i2 + 1);
	}
	memset(vis, 0, sizeof(vis));
	for(int i=0; i<n; i++){
		if(vis[i]) continue;
		if(sz(gph[i]) == 2){
			if(gph[i][0] == gph[i][1]){
				printf("%d %d\n", i + 1, gph[i][0] + 1);
				vis[i] = vis[gph[i][0]] = 1;
				continue;
			}
		}
	}
}

Compilation message

matching.cpp: In function 'int main()':
matching.cpp:263:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~
matching.cpp:187:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
matching.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].x,&a[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 157176 KB Output is correct
2 Correct 195 ms 157304 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 157176 KB Output is correct
2 Correct 195 ms 157304 KB Output is correct
3 Correct 208 ms 157260 KB Output is correct
4 Correct 193 ms 157280 KB Output is correct
5 Correct 201 ms 157180 KB Output is correct
6 Correct 188 ms 156792 KB Output is correct
7 Correct 187 ms 156924 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 157176 KB Output is correct
2 Correct 195 ms 157304 KB Output is correct
3 Correct 208 ms 157260 KB Output is correct
4 Correct 193 ms 157280 KB Output is correct
5 Correct 201 ms 157180 KB Output is correct
6 Correct 188 ms 156792 KB Output is correct
7 Correct 187 ms 156924 KB Output is correct
8 Correct 205 ms 157432 KB Output is correct
9 Correct 240 ms 157308 KB Output is correct
10 Correct 190 ms 157304 KB Output is correct
11 Correct 214 ms 156920 KB Output is correct
12 Correct 190 ms 157304 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 157176 KB Output is correct
2 Correct 195 ms 157304 KB Output is correct
3 Correct 208 ms 157260 KB Output is correct
4 Correct 193 ms 157280 KB Output is correct
5 Correct 201 ms 157180 KB Output is correct
6 Correct 188 ms 156792 KB Output is correct
7 Correct 187 ms 156924 KB Output is correct
8 Correct 205 ms 157432 KB Output is correct
9 Correct 240 ms 157308 KB Output is correct
10 Correct 190 ms 157304 KB Output is correct
11 Correct 214 ms 156920 KB Output is correct
12 Correct 190 ms 157304 KB Output is correct
13 Correct 215 ms 159992 KB Output is correct
14 Correct 217 ms 160032 KB Output is correct
15 Correct 216 ms 159864 KB Output is correct
16 Correct 263 ms 160120 KB Output is correct
17 Correct 215 ms 159996 KB Output is correct
18 Correct 265 ms 159992 KB Output is correct
19 Correct 232 ms 160120 KB Output is correct
20 Correct 215 ms 159992 KB Output is correct
21 Correct 205 ms 159608 KB Output is correct
22 Correct 68 ms 105592 KB Output is correct
23 Correct 212 ms 160248 KB Output is correct
24 Correct 216 ms 159924 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 157176 KB Output is correct
2 Correct 195 ms 157304 KB Output is correct
3 Correct 208 ms 157260 KB Output is correct
4 Correct 193 ms 157280 KB Output is correct
5 Correct 201 ms 157180 KB Output is correct
6 Correct 188 ms 156792 KB Output is correct
7 Correct 187 ms 156924 KB Output is correct
8 Correct 205 ms 157432 KB Output is correct
9 Correct 240 ms 157308 KB Output is correct
10 Correct 190 ms 157304 KB Output is correct
11 Correct 214 ms 156920 KB Output is correct
12 Correct 190 ms 157304 KB Output is correct
13 Correct 215 ms 159992 KB Output is correct
14 Correct 217 ms 160032 KB Output is correct
15 Correct 216 ms 159864 KB Output is correct
16 Correct 263 ms 160120 KB Output is correct
17 Correct 215 ms 159996 KB Output is correct
18 Correct 265 ms 159992 KB Output is correct
19 Correct 232 ms 160120 KB Output is correct
20 Correct 215 ms 159992 KB Output is correct
21 Correct 205 ms 159608 KB Output is correct
22 Correct 68 ms 105592 KB Output is correct
23 Correct 212 ms 160248 KB Output is correct
24 Correct 216 ms 159924 KB Output is correct
25 Correct 1356 ms 297096 KB Output is correct
26 Correct 1379 ms 296940 KB Output is correct
27 Correct 1322 ms 297036 KB Output is correct
28 Correct 1406 ms 297012 KB Output is correct
29 Correct 1383 ms 296944 KB Output is correct
30 Correct 1242 ms 296644 KB Output is correct
31 Correct 1288 ms 296916 KB Output is correct
32 Correct 1266 ms 296684 KB Output is correct
33 Correct 1295 ms 282480 KB Output is correct
34 Correct 129 ms 109560 KB Output is correct
35 Correct 142 ms 109688 KB Output is correct
36 Correct 2114 ms 292764 KB Output is correct
37 Correct 1105 ms 289128 KB Output is correct
38 Correct 1124 ms 291048 KB Output is correct