Submission #877019

#	Time	Username	Problem	Language	Result	Execution time	Memory
877019		fanwen	Joker (BOI20_joker)	C++17	100 / 100	200 ms	47544 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \

const int MAX = 5e5 + 5;

struct Edge {
	int u, v;
	int get(int x) {
		return x ^ u ^ v;
	}
} e[MAX];

int n, m, q;
vector <int> adj[MAX];

namespace sub1 {
	bool check() {
		return max({n, m, q}) <= 5000;
	}

	int dd[MAX];

	bool solve(int l, int r) {

		fill(dd + 1, dd + n + 1, -1);
		bool ans = true;
		function <void(int, int)> 
		dfs = [&] (int u, int c) {
			dd[u] = c;
			for (int i : adj[u]) if(i < l || i > r) {
				int v = e[i].get(u);
				if(dd[v] == -1) {
					dfs(v, 1 ^ c);
				} else {
					if(c == dd[v]) {
						ans = false;
					}
				}
			}
		};
		for (int u = 1; u <= n; ++u) if(dd[u] == -1) {
			dfs(u, 0);
		}
		return ans;
	}

	void solve() {
		while(q--) {
			int l, r; cin >> l >> r;
			cout << (solve(l, r) ? "NO" : "YES") << '\n';
		}
		exit(0);
	}
}

struct Query {
	int l, r, id;
} queries[MAX];

int ans[MAX];

namespace sub2 {

	bool check() {
		for (int i = 1; i <= q; ++i) {
			if(queries[i].l != 1) {
				return false;
			}
		}
		return true;
	}

	int rank[MAX];
	pair <int, int> par[MAX];
	bool bipartite[MAX];

	void make_set(int v) {
		par[v] = make_pair(v, 0);
		rank[v] = 0;
		bipartite[v] = true;
	}

	pair <int, int> find_set(int u) {
		if(u != par[u].fi) {
			int parity = par[u].se;
			par[u] = find_set(par[u].fi);
			par[u].se ^= parity;
		}
		return par[u];
	}

	bool total = true;

	bool merge(int a, int b) {
		pair <int, int> pa = find_set(a); a = pa.fi; int x = pa.se;
		pair <int, int> pb = find_set(b); b = pb.fi; int y = pb.se;

		if(a == b) {
			if(x == y) {
				bipartite[a] = false;
				total = false;
			}
			return false;
		}

		if(rank[a] < rank[b]) swap(a, b);

		par[b] = make_pair(a, 1 ^ x ^ y);

		bipartite[a] &= bipartite[b];
		if(rank[a] == rank[b]) rank[a]++;
		return true;
	}

	void solve() {
		sort(queries + 1, queries + q + 1, [&] (const Query &a, const Query &b) {
			return a.r > b.r;
		});

		int j = m;
		for (int i = 1; i <= n; ++i) make_set(i);
		for (int i = 1; i <= q; ++i) {
			while(j >= 1 && j > queries[i].r) {
				merge(e[j].u, e[j].v);
				j--;
			}
			ans[queries[i].id] = total;
		}
		for (int i = 1; i <= q; ++i) {
			cout << (ans[i] ? "NO" : "YES") << '\n';
		}
		exit(0);
	}
}

namespace sub3 {

	bool check() {
		return true;
	}

	struct save {
		int u, v, ranku, rankv, res, cnt;
	};

	vector <save> tmp;
	int res = true;

	int lab[MAX], wei[MAX], dp[MAX];

	int find(int u) {
		return lab[u] < 0 ? u : find(lab[u]);
	}

	int get_w(int u) {
		return lab[u] < 0 ? 0 : wei[u] ^ get_w(lab[u]);
	}

	bool merge(int u, int v, int cnt) {
		if(!res) return false;
		int w = 1 ^ get_w(u) ^ get_w(v);
		u = find(u), v = find(v);
		assert(u != 0 && v != 0);
		if(lab[u] > lab[v]) swap(u, v);
		tmp.push_back({u, v, lab[u], lab[v], res, cnt});
		if(u == v) {
			if(w) res = false;
			return w == 0;
		}

		lab[u] += lab[v];
		lab[v] = u;
		wei[v] = w;
		return true;
	}

	void rollback(int l, int r) {
		if(l > r) return;
		while(!tmp.empty() && tmp.back().cnt >= l && tmp.back().cnt <= r) {
			auto [u, v, labu, labv, x, _] = tmp.back(); tmp.pop_back();
			lab[u] = labu, lab[v] = labv;
			wei[v] = 0;
			res = x;
		}
	}

	void dnc(int l, int r, int optL, int optR) {
		if(l > r) return;
		int mid = l + r >> 1;
		for (int i = l; i < mid; i++) {
			merge(e[i].u, e[i].v, i);
		}
		int optM = max(mid, optL) - 1;

		for (int i = optR; i >= max(mid, optL); --i) {
			if(!res) {
				optM = i;
				break;
			}
			merge(e[i].u, e[i].v, i);
		}

		dp[mid] = ++optM;

		optM = min(m, optM);

		rollback(optM, optR);

		merge(e[mid].u, e[mid].v, mid);

		dnc(mid + 1, r, optM, optR);

		rollback(l, mid);

		for (int i = optM + 1; i <= optR; ++i) {
			merge(e[i].u, e[i].v, i);
		}

		dnc(l, mid - 1, optL, optM);

		rollback(optM + 1, optR);
	}

	void solve() {

		memset(lab, -1, sizeof lab);
		dnc(1, m, 1, m);
		for (int i = 1; i <= q; ++i) {
			int l = queries[i].l, r = queries[i].r;
			cout << (dp[l] > r ? "YES" : "NO") << '\n';
		}
	}
}

void you_make_it(void) {
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) {
    	cin >> e[i].u >> e[i].v;
    	adj[e[i].u].push_back(i);
    	adj[e[i].v].push_back(i);
    }
    // if(sub1::check()) sub1::solve();
    for (int i = 1; i <= q; ++i) cin >> queries[i].l >> queries[i].r, queries[i].id = i;
    if(sub3::check()) sub3::solve();
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("joker");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

Joker.cpp: In function 'void sub3::dnc(int, int, int, int)':
Joker.cpp:197:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  197 |   int mid = l + r >> 1;
      |             ~~^~~
Joker.cpp: In function 'int main()':
Joker.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:261:5: note: in expansion of macro 'file'
  261 |     file("joker");
      |     ^~~~
Joker.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:261:5: note: in expansion of macro 'file'
  261 |     file("joker");
      |     ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29