oj.uz

Submission #299542

# Submission time Handle Problem Language Result Execution time Memory
299542 2020-09-15T07:14:26 Z E869120 Joker (BOI20_joker) C++14
25 / 100
 321 ms 27044 KB 
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
	public:
	vector<int> par;
	
	void init(int sz) {
		par.resize(sz, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u);
		v = root(v);
		if (u == v) return;
		par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

// Input
int N;
int M, A[1 << 18], B[1 << 18];
int Q, L[1 << 18], R[1 << 18];

// Graph
vector<int> X[1 << 18];
int col[1 << 18];
bool flag;

// Subtask3
vector<pair<int, int>> Y[1 << 18];
int lim[1 << 18];
bool used[1 << 18];

void henhari(int idx) {
	for (int i = 1; i <= N; i++) Y[i].clear();
	for (int i = 1; i <= idx; i++) {
		if (used[i] == false) continue;
		Y[A[i]].push_back(make_pair(B[i], 1000000000));
		Y[B[i]].push_back(make_pair(A[i], 1000000000));
	}
	for (int i = idx + 1; i <= M; i++) {
		if (used[i] == false) continue;
		Y[A[i]].push_back(make_pair(B[i], i));
		Y[B[i]].push_back(make_pair(A[i], i));
	}
}

void dfs2(int pos, int dep) {
	col[pos] = dep;
	for (pair<int, int> i : Y[pos]) {
		if (col[i.first] >= 0) continue;
		dfs2(i.first, dep ^ 1);
	}
}

void coloring() {
	for (int i = 1; i <= N; i++) col[i] = -1;
	for (int i = 1; i <= N; i++) {
		if (col[i] >= 0) continue;
		dfs2(i, 0);
	}
}

int dfs3(int pos, int to, int pre) {
	if (pos == to) return (1 << 30);
	int ret = 0;
	for (pair<int, int> i : Y[pos]) {
		if (i.first == pre) continue;
		int z = dfs3(i.first, to, pos);
		ret = max(ret, min(z, i.second));
	}
	return ret;
}

int getedge(int a, int b) {
	return dfs3(a, b, -1);
}

void solve_subtask3() {
	int maxL = 0;
	for (int i = 1; i <= Q; i++) maxL = max(maxL, L[i]);
	
	// Step #1. Maeshori
	UnionFind UF;
	UF.init(N + 2);
	for (int i = M; i >= 1; i--) {
		if (UF.same(A[i], B[i]) == true) continue;
		UF.unite(A[i], B[i]);
		used[i] = true;
	}
	
	// Step #2. Maeshori 2
	henhari(0);
	coloring();
	
	// Step #3. Get Answer
	for (int i = 1; i <= maxL; i++) {
		for (int j = i; j <= M; j++) {
			if (used[j] == false && col[A[j]] == col[B[j]]) lim[i] = j;
		}
		int v = getedge(A[i], B[i]);
		//cout << i << ": " << v << endl;
		used[v] = false;
		used[i] = true;
		henhari(i);
		coloring();
	}
	
	// Step #4. Output
	for (int i = 1; i <= Q; i++) {
		if (lim[L[i]] > R[i]) printf("YES\n");
		else printf("NO\n");
	}
}

void dfs(int pos, int dep) {
	col[pos] = dep;
	for (int i : X[pos]) {
		if (col[i] != -1) {
			if (col[i] == dep) flag = true;
			continue;
		}
		dfs(i, dep ^ 1);
	}
}

bool solve(int l, int r) {
	flag = false;
	for (int i = 1; i <= N; i++) X[i].clear();
	for (int i = 1; i <= M; i++) {
		if (l <= i && i <= r) continue;
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	for (int i = 1; i <= N; i++) col[i] = -1;
	for (int i = 1; i <= N; i++) {
		if (col[i] >= 0) continue;
		dfs(i, 0);
	}
	return flag;
}

void solve_subtask1() {
	for (int i = 1; i <= Q; i++) {
		bool ans = solve(L[i], R[i]);
		if (ans == false) printf("NO\n");
		else printf("YES\n");
	}
}

int main() {
	scanf("%d%d%d", &N, &M, &Q);
	for (int i = 1; i <= M; i++) scanf("%d%d", &A[i], &B[i]);
	for (int i = 1; i <= Q; i++) scanf("%d%d", &L[i], &R[i]);
	
	if (N <= 0 && M <= 2000 && Q <= 2000) solve_subtask1();
	else solve_subtask3();
	return 0;
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  161 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:162:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |  for (int i = 1; i <= M; i++) scanf("%d%d", &A[i], &B[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:163:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |  for (int i = 1; i <= Q; i++) scanf("%d%d", &L[i], &R[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 11 ms 12672 KB Output is correct
4 Runtime error 28 ms 25440 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 11 ms 12672 KB Output is correct
4 Runtime error 28 ms 25440 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 162 ms 26744 KB Output is correct
4 Correct 224 ms 27044 KB Output is correct
5 Correct 290 ms 24824 KB Output is correct
6 Correct 156 ms 21368 KB Output is correct
7 Correct 175 ms 20984 KB Output is correct
8 Correct 156 ms 19576 KB Output is correct
9 Correct 200 ms 21240 KB Output is correct
10 Correct 313 ms 24696 KB Output is correct
11 Correct 191 ms 21336 KB Output is correct
12 Correct 245 ms 24436 KB Output is correct
13 Correct 139 ms 17496 KB Output is correct
14 Correct 151 ms 19320 KB Output is correct
15 Correct 255 ms 22620 KB Output is correct
16 Correct 321 ms 24440 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 11 ms 12672 KB Output is correct
4 Runtime error 28 ms 25440 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 11 ms 12672 KB Output is correct
4 Runtime error 28 ms 25440 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 11 ms 12672 KB Output is correct
4 Runtime error 28 ms 25440 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -