oj.uz

Submission #201253

# Submission time Handle Problem Language Result Execution time Memory
201253 2020-02-10T03:28:07 Z gs14004 Matching (COCI20_matching) C++17
18 / 110
 233 ms 159996 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 << 28)) 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 << 28));
	}
	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, ~j.second);
			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(pi(a[gph[i][0]].x, a[gph[i][0]].y) == pi(a[i].x, a[i].y)){
				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");
	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(pi(a[gph[i][0]].x, a[gph[i][0]].y) == pi(a[i].x, a[i].y)){
				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: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 204 ms 157304 KB Output is correct
2 Correct 200 ms 157176 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 157304 KB Output is correct
2 Correct 200 ms 157176 KB Output is correct
3 Correct 195 ms 157304 KB Output is correct
4 Correct 204 ms 157176 KB Output is correct
5 Correct 197 ms 157432 KB Output is correct
6 Correct 196 ms 156920 KB Output is correct
7 Correct 199 ms 156792 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 157304 KB Output is correct
2 Correct 200 ms 157176 KB Output is correct
3 Correct 195 ms 157304 KB Output is correct
4 Correct 204 ms 157176 KB Output is correct
5 Correct 197 ms 157432 KB Output is correct
6 Correct 196 ms 156920 KB Output is correct
7 Correct 199 ms 156792 KB Output is correct
8 Correct 203 ms 157372 KB Output is correct
9 Correct 202 ms 157328 KB Output is correct
10 Correct 199 ms 157304 KB Output is correct
11 Correct 194 ms 156920 KB Output is correct
12 Correct 197 ms 157304 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 157304 KB Output is correct
2 Correct 200 ms 157176 KB Output is correct
3 Correct 195 ms 157304 KB Output is correct
4 Correct 204 ms 157176 KB Output is correct
5 Correct 197 ms 157432 KB Output is correct
6 Correct 196 ms 156920 KB Output is correct
7 Correct 199 ms 156792 KB Output is correct
8 Correct 203 ms 157372 KB Output is correct
9 Correct 202 ms 157328 KB Output is correct
10 Correct 199 ms 157304 KB Output is correct
11 Correct 194 ms 156920 KB Output is correct
12 Correct 197 ms 157304 KB Output is correct
13 Correct 212 ms 159992 KB Output is correct
14 Correct 219 ms 159992 KB Output is correct
15 Correct 217 ms 159956 KB Output is correct
16 Correct 217 ms 159996 KB Output is correct
17 Correct 220 ms 159864 KB Output is correct
18 Correct 211 ms 159992 KB Output is correct
19 Correct 233 ms 159992 KB Output is correct
20 Correct 224 ms 159992 KB Output is correct
21 Correct 213 ms 159608 KB Output is correct
22 Incorrect 216 ms 159992 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 157304 KB Output is correct
2 Correct 200 ms 157176 KB Output is correct
3 Correct 195 ms 157304 KB Output is correct
4 Correct 204 ms 157176 KB Output is correct
5 Correct 197 ms 157432 KB Output is correct
6 Correct 196 ms 156920 KB Output is correct
7 Correct 199 ms 156792 KB Output is correct
8 Correct 203 ms 157372 KB Output is correct
9 Correct 202 ms 157328 KB Output is correct
10 Correct 199 ms 157304 KB Output is correct
11 Correct 194 ms 156920 KB Output is correct
12 Correct 197 ms 157304 KB Output is correct
13 Correct 212 ms 159992 KB Output is correct
14 Correct 219 ms 159992 KB Output is correct
15 Correct 217 ms 159956 KB Output is correct
16 Correct 217 ms 159996 KB Output is correct
17 Correct 220 ms 159864 KB Output is correct
18 Correct 211 ms 159992 KB Output is correct
19 Correct 233 ms 159992 KB Output is correct
20 Correct 224 ms 159992 KB Output is correct
21 Correct 213 ms 159608 KB Output is correct
22 Incorrect 216 ms 159992 KB Output isn't correct
23 Halted 0 ms 0 KB -