oj.uz

Submission #916233

# Submission time Handle Problem Language Result Execution time Memory
916233 2024-01-25T14:09:08 Z NK_ Inside information (BOI21_servers) C++17
5 / 100
 223 ms 39768 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();
		// cout << u << " <-> " << v << endl;
		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<void(int, int, int)> dfs = [&](int u, int t, int id) {
		vi chd; sort(begin(adj[u]), end(adj[u]), [&](pi x, pi y) {
			return x.s > y.s;
		});
		
		S.emplace_back(); int nid = ++cur; bool done = 0;
		for(auto& e : adj[u]) if (e.s != t) {
			int v, tv; tie(v, tv) = e;	

			swap(T[u], T[v]);

			if (t > tv) {
				if (!done) merge(id, nid), done = 1;
				S[id].insert(tv);
				dfs(v, tv, id);
				chd.pb(tv);
			} else {
				S[nid].insert(tv);
				dfs(v, tv, nid);

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

			swap(T[u], T[v]);

		}

		if (!done) merge(id, nid), done = 1;

		// 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");
			}
		}	

		// cout << "U: " << id << " " << nid << endl;

		reverse(begin(chd), end(chd));
		for(auto& p : chd) {
			S[id].erase(p); 
			rollback();
		}
	};

	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 Correct 21 ms 5980 KB Output is correct
2 Incorrect 35 ms 8532 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5980 KB Output is correct
2 Incorrect 35 ms 8532 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5976 KB Output is correct
2 Correct 217 ms 38596 KB Output is correct
3 Correct 223 ms 39768 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5976 KB Output is correct
2 Correct 217 ms 38596 KB Output is correct
3 Correct 223 ms 39768 KB Output is correct
4 Correct 24 ms 5932 KB Output is correct
5 Correct 213 ms 39000 KB Output is correct
6 Correct 144 ms 38200 KB Output is correct
7 Correct 150 ms 37576 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5980 KB Output is correct
2 Incorrect 30 ms 8340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5980 KB Output is correct
2 Incorrect 30 ms 8340 KB Output isn't correct
3 Halted 0 ms 0 KB -