oj.uz

답안 #256165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256165 2020-08-02T10:45:07 Z 구재현(#5035) Joker (BOI20_joker) C++17
0 / 100
 1 ms 1920 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 400005;

struct event{
	int *p;
	int v;
};

int n, m, q;
pi a[MAXN];

void rollback(vector<event> &E){
	reverse(all(E));
	for(auto &i : E){
		*i.p = i.v;
	}
	E.clear();
}

struct btracker{
	int pa[MAXN], rk[MAXN];
	int is_cycle;
	void init(int n){
		iota(pa, pa + n + 1, 0);
		memset(rk, 0, sizeof(rk));
		is_cycle = 0;
	}
	int find(int x){
		return pa[x] == x ? x : find(pa[x]);
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		if(rk[p] > rk[q]) swap(p, q);
		pa[p] = q;
		if(rk[p] == rk[q]) rk[q]++;
		return 1;
	}
	bool uni(int p, int q, vector<event> &snap){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		if(rk[p] > rk[q]) swap(p, q);
		snap.push_back((event){&pa[p], pa[p]});
		pa[p] = q;
		if(rk[p] == rk[q]){
			snap.push_back((event){&rk[q], rk[q]});
			rk[q]++;
		}
		return 1;
	}
	void add_edge(int x, int y){
		uni(x, y + n);
		uni(y, x + n);
		if(find(x) == find(x + n)) is_cycle = 1;
	}
	void add_edge(int x, int y, vector<event> &snap){
		uni(x, y + n, snap);
		uni(y, x + n, snap);
		if(find(x) == find(x + n)){
			snap.push_back((event){&is_cycle, is_cycle});
			is_cycle = 1;
		}
	}
}disj;

int dap[MAXN];

void solve(int s, int e, int ps, int pe){
}

int main(){
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1; i<=m; i++){
		scanf("%d %d",&a[i].first,&a[i].second);
		a[i + m] = a[i];
	}
	disj.init(n+n);
	int stpos = -1;
	for(int i=m; i; i--){
		disj.add_edge(a[i].first, a[i].second);
		if(disj.is_cycle){
			stpos = i + 1;
			break;
		}
	}
	if(disj.is_cycle == 0){
		while(q--) puts("YES");
		return 0;
	}
	disj.init(n+n);
	for(int i=stpos; i<=m+1; i++){
		vector<event> v;
		dap[i] = 2 * m;
		for(int j=i; j<=2*m; j++){
			disj.add_edge(a[j].first, a[j].second, v);
			if(disj.is_cycle){
				dap[i] = j - 1;
				break;
			}
		}
		rollback(v);
	}
	//solve(stpos, m + 1, m + 1, 2 * m);
	while(q--){
		int x, y; scanf("%d %d",&x,&y);
		puts(dap[y + 1] >= x + m ? "YES" : "NO");
	}
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
Joker.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first,&a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:113:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d %d",&x,&y);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -