Submission #299542

#	Time	Username	Problem	Language	Result	Execution time	Memory
299542		E869120	Joker (BOI20_joker)	C++14	25 / 100	321 ms	27044 KiB

Joker

#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 (stderr)

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
• Subtask 2: 0 / 8
• Subtask 3: 25 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29