oj.uz

Submission #201260

# Submission time Handle Problem Language Result Execution time Memory
201260 2020-02-10T04:32:47 Z gs14004 Matching (COCI20_matching) C++17
18 / 110
 376 ms 323960 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);
			}
			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), cnt++;
		if(i.cmp >= 0 && ans[i.cmp]) printf("%d %d\n", i.i1 + 1, i.i2 + 1), cnt++;
	}
	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);
				cnt++;
				vis[i] = vis[gph[i][0]] = 1;
				continue;
			}
		}
	}
	assert(cnt*2 == n);
}

Compilation message

matching.cpp: In function 'int main()':
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 199 ms 157176 KB Output is correct
2 Correct 193 ms 157304 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 157176 KB Output is correct
2 Correct 193 ms 157304 KB Output is correct
3 Correct 194 ms 157220 KB Output is correct
4 Correct 196 ms 157176 KB Output is correct
5 Correct 201 ms 157304 KB Output is correct
6 Correct 199 ms 156920 KB Output is correct
7 Correct 195 ms 156920 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 157176 KB Output is correct
2 Correct 193 ms 157304 KB Output is correct
3 Correct 194 ms 157220 KB Output is correct
4 Correct 196 ms 157176 KB Output is correct
5 Correct 201 ms 157304 KB Output is correct
6 Correct 199 ms 156920 KB Output is correct
7 Correct 195 ms 156920 KB Output is correct
8 Correct 217 ms 157352 KB Output is correct
9 Correct 196 ms 157308 KB Output is correct
10 Correct 193 ms 157304 KB Output is correct
11 Correct 196 ms 156920 KB Output is correct
12 Correct 193 ms 157304 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 157176 KB Output is correct
2 Correct 193 ms 157304 KB Output is correct
3 Correct 194 ms 157220 KB Output is correct
4 Correct 196 ms 157176 KB Output is correct
5 Correct 201 ms 157304 KB Output is correct
6 Correct 199 ms 156920 KB Output is correct
7 Correct 195 ms 156920 KB Output is correct
8 Correct 217 ms 157352 KB Output is correct
9 Correct 196 ms 157308 KB Output is correct
10 Correct 193 ms 157304 KB Output is correct
11 Correct 196 ms 156920 KB Output is correct
12 Correct 193 ms 157304 KB Output is correct
13 Correct 208 ms 160120 KB Output is correct
14 Correct 210 ms 159992 KB Output is correct
15 Correct 205 ms 159864 KB Output is correct
16 Correct 218 ms 160120 KB Output is correct
17 Correct 214 ms 159884 KB Output is correct
18 Correct 219 ms 159992 KB Output is correct
19 Correct 228 ms 159992 KB Output is correct
20 Correct 211 ms 159992 KB Output is correct
21 Correct 212 ms 159584 KB Output is correct
22 Runtime error 376 ms 323960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 157176 KB Output is correct
2 Correct 193 ms 157304 KB Output is correct
3 Correct 194 ms 157220 KB Output is correct
4 Correct 196 ms 157176 KB Output is correct
5 Correct 201 ms 157304 KB Output is correct
6 Correct 199 ms 156920 KB Output is correct
7 Correct 195 ms 156920 KB Output is correct
8 Correct 217 ms 157352 KB Output is correct
9 Correct 196 ms 157308 KB Output is correct
10 Correct 193 ms 157304 KB Output is correct
11 Correct 196 ms 156920 KB Output is correct
12 Correct 193 ms 157304 KB Output is correct
13 Correct 208 ms 160120 KB Output is correct
14 Correct 210 ms 159992 KB Output is correct
15 Correct 205 ms 159864 KB Output is correct
16 Correct 218 ms 160120 KB Output is correct
17 Correct 214 ms 159884 KB Output is correct
18 Correct 219 ms 159992 KB Output is correct
19 Correct 228 ms 159992 KB Output is correct
20 Correct 211 ms 159992 KB Output is correct
21 Correct 212 ms 159584 KB Output is correct
22 Runtime error 376 ms 323960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -