oj.uz

Submission #916225

# Submission time Handle Problem Language Result Execution time Memory
916225 2024-01-25T14:00:13 Z NK_ Inside information (BOI21_servers) C++17
5 / 100
 251 ms 41432 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair
#define pb push_back


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using pi = pair<int, int>;

template<class T> using V = vector<T>;
using vi = V<int>;
using vpi = V<pi>;

const int INF = 1e9;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K; cin >> N >> K;

	V<vpi> adj(N); V<vpi> Q(N);
	for(int i = 0; i < (N + K - 1); i++) {
		char c; cin >> c;
		if (c == 'S') {
			int x, y; cin >> x >> y; --x, --y;
			adj[x].pb(mp(y, i));
			adj[y].pb(mp(x, i));
		}

		if (c == 'C') {
			int x; cin >> x; --x;
			Q[x].pb(mp(i, -1)); // (t, operation type)
		}

		if (c == 'Q') {
			int u, x; cin >> u >> x; --u, --x;
			Q[x].pb(mp(i, u)); // (t, operation type)
		}
	}

	vi T(N, -1);
	function <void(int, int)> gen = [&](int u, int p) {
		for(auto& e : adj[u]) if (e.f != p) {
			T[e.f] = e.s; gen(e.f, u);
		}
	};
	gen(0, -1);

	V<iset<int>> S(1); int cur = 0;

	V<array<int, 3>> his;

	auto rollback = [&]() {
		auto [u, v, swp] = his.back(); his.pop_back();
		for(auto& p : S[v]) S[u].erase(p);
		if (swp) S[u].swap(S[v]);
	};			

	auto merge = [&](int u, int v) {
		bool swp = 0;
		if (sz(S[u]) < sz(S[v])) S[u].swap(S[v]), swp = 1;
		for(auto& p : S[v]) S[u].insert(p);
		his.pb({u, v, swp});
	};

	V<string> ans(N + K - 1, "NK");

	function<int(int, int, int)> dfs = [&](int u, int t, int id) {
		vpi chd; sort(begin(adj[u]), end(adj[u]), [&](pi x, pi y) {
			return x.s > y.s;
		});

		int merges = 0;
		
		S.emplace_back(); int nid = ++cur; 
		for(auto& e : adj[u]) if (e.s != t) {
			int v, tv; tie(v, tv) = e;	
			swap(T[u], T[v]);
			if (t > tv) {
				S[id].insert(tv);
				int rolls = dfs(v, tv, id);
				chd.pb(mp(tv, rolls));
			} else {
				S[nid].insert(tv);
				dfs(v, tv, nid);

				// cout << "MERGE" << endl;
				// cout << v << " " << nid << " => ";
				// for(auto& x : S[nid]) cout << x << " ";
				// cout << endl;

				// cout << u << " " << id << " => ";
				// for(auto& x : S[id]) cout << x << " ";
				// cout << endl;

				merge(id, nid); merges++;
			}
			swap(T[u], T[v]);

			// cout << u << " " << id << " => ";
			// for(auto& x : S[id]) cout << x << " ";
			// cout << endl;
		}

		

		for(auto& p : Q[u]) {
			if (p.s == -1) {
				// cout << p.f << endl;
				// C -> count entries with t <= T
				ans[p.f] = to_string(S[id].order_of_key(p.f + 1) + 1);
			} else {
				// cout << p.f << " " << p.s << " ==> " << T[p.s] << endl;
				// Q -> check if p.s is connect at tie p.f
				if (p.s == u) ans[p.f] = "yes";
				else ans[p.f] = (T[p.s] <= p.f && S[id].find(T[p.s]) != S[id].end() ? "yes" : "no");
			}
		}

		for(auto& p : chd) {
			S[id].erase(p.f); while(p.s--) rollback();
		}

		// cout << u << " " << id << " => ";
		// for(auto& x : S[id]) cout << x << " ";
		// cout << endl << endl << endl;

		return merges;
	};

	dfs(0, INF, 0);

	for(int i = 0; i < (N + K - 1); i++) {
		if (ans[i] == "NK") continue;
		cout << ans[i] << nl;
	}

	exit(0-0);
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 6992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 6992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6856 KB Output is correct
2 Correct 251 ms 41432 KB Output is correct
3 Correct 227 ms 41296 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6856 KB Output is correct
2 Correct 251 ms 41432 KB Output is correct
3 Correct 227 ms 41296 KB Output is correct
4 Correct 20 ms 6996 KB Output is correct
5 Correct 194 ms 40644 KB Output is correct
6 Correct 160 ms 39984 KB Output is correct
7 Correct 143 ms 39876 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 7004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 7004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 6908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 6908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 7160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 7160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 6860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 6860 KB Output isn't correct
2 Halted 0 ms 0 KB -