oj.uz

답안 #1043125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043125 2024-08-04T00:43:35 Z wood Joker (BOI20_joker) C++17
25 / 100
 1403 ms 5128 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

struct dsu{
	vector<bool> side;
	vector<int> rep, size;
	dsu(int n){
		for(int i = 0; i<n; i++){
			rep.pb(i);
			side.pb(0);
			size.pb(1);
		}
	}
	int get(int u){
		if(u == rep[u]) return u;
		int oldparent = rep[u];
		rep[u] = get(rep[u]);
		side[u] = side[u]^side[oldparent];
		return rep[u];
	}
	void merge(int u, int v){
		int oldu = u, oldv = v;
		u = get(u); v = get(v);
		if(size[v]>size[u]){
		       	swap(u,v);
			swap(oldu, oldv);
		 }
		side[v] = !(side[oldv]^side[oldu]);
		size[u]+=size[v];
		rep[v] = u;
	}
};

int main() {
#ifndef ONLINE_JUDGE
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,q; cin>>n>>m>>q;
	vector<pair<int,int>> e;
	for(int i = 0; i<m; i++){
		int a,b; cin>>a>>b;
		a--; b--;
		e.emplace_back(a,b);
	}
	int result[200];
	for(int ii = 0; ii<200; ii++) {
		dsu D(n);
		for(int kk = 0; kk<min(ii,m); kk++) {
			if(D.get(e[kk].first)!=D.get(e[kk].second))
				D.merge(e[kk].first, e[kk].second);
			else if(D.side[e[kk].first]==D.side[e[kk].second]){
				result[ii] = INT_MAX;
				goto fail;
			}
		}
		for(int i = m-1; i>=ii; i--) {
			int l = e[i].first, r = e[i].second;
			if(D.get(l)!=D.get(r))
				D.merge(l,r);
			else if(D.side[l]==D.side[r]){
				result[ii] = i;
				break;
			}
		}
		fail:
		continue;
	}
	for(int j = 0; j<q; j++){
		int l,b; cin>>l>>b;
		l--;
		if(b>result[l]) cout<<"NO\n";
		else cout<<"YES\n";
	}	
	return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 600 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 600 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 513 ms 3776 KB Output is correct
4 Correct 1403 ms 4972 KB Output is correct
5 Correct 337 ms 5056 KB Output is correct
6 Correct 155 ms 3784 KB Output is correct
7 Correct 158 ms 3776 KB Output is correct
8 Correct 312 ms 3372 KB Output is correct
9 Correct 334 ms 4040 KB Output is correct
10 Correct 822 ms 5088 KB Output is correct
11 Correct 539 ms 3776 KB Output is correct
12 Correct 716 ms 5128 KB Output is correct
13 Correct 260 ms 2828 KB Output is correct
14 Correct 272 ms 3352 KB Output is correct
15 Correct 659 ms 4520 KB Output is correct
16 Correct 859 ms 5068 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 600 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 600 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 600 KB Output isn't correct
8 Halted 0 ms 0 KB -