Submission #1261624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261624		Bui_Quoc_Cuong	Collapse (JOI18_collapse)	C++20	0 / 100	18 ms	3524 KiB

collapse

#include <bits/stdc++.h>
// #include "collapse.h"
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define all(a) a.begin(), a.end()
#define pb push_back
#define fi first
#define se second
const int maxN = 1e5 + 5;

int n, m, q;
array <int, 3> edges[maxN];
array <int, 2> Q[maxN];

void init() {
	cin >> n >> m >> q;
	FOR(i, 1, m) {
		cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
		if (edges[i][1] > edges[i][2]) swap(edges[i][1], edges[i][2]);
	}
	FOR(i, 1, q) {
		cin >> Q[i][0] >> Q[i][1];
	}
}

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

	set <int> G[5005];
	bool vis[5005];

	void dfs(int u, int p) {
		if (vis[u]) return;
		vis[u] = 1;
		for(auto v : G[u]) if (v != p && vis[v] == 0) {
			dfs(v, u);
		}
	}

	vector <int> solve() {
		vector <int> res;
		FOR(_q, 1, q) {
			FOR(i, 1, n) G[i].clear();
			int ssc = 0;

			FOR(i, 1, Q[_q][0] + 1) {
				if (edges[i][0] == 1) {
					int u = edges[i][1], v = edges[i][2];
					if (u <= Q[_q][1] && v >= Q[_q][1] + 1) continue;
					G[u].erase(v);
					G[v].erase(u);	 
				} else {
					int u = edges[i][1], v = edges[i][2];
					if (u <= Q[_q][1] && v >= Q[_q][1] + 1) continue;
					G[u].insert(v);
					G[v].insert(u);
				}
			}

			FOR(i, 1, n) vis[i] = 0;
			FOR(i, 1, n) if (!vis[i]) {
				ssc++;
				dfs(i, i);
			}

			res.push_back(ssc);
		}
		return res;
	}	
}

vector <int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
	n = N + 1;
	m = X.size();
	q = W.size();
	FOR(i, 0, m - 1) {
		edges[i + 1][0] = T[i];
		edges[i + 1][1] = X[i] + 1;
		edges[i + 1][2] = Y[i] + 1;
		if (edges[i + 1][1] > edges[i + 1][2]) swap(edges[i + 1][1], edges[i + 1][2]);
	}
	for (int i = 0; i < q; i++) {
		Q[i + 1][0] = W[i] + 1;
		Q[i + 1][1] = P[i] + 1;
	}	
	vector <int> res = sub1::solve();
	return res;
}

void process() {
	vector <int> res;
	if(sub1::checksub()) res = sub1::solve();
	for (int &val : res) cout << val << " ";
}

// signed main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     #define ko "kieuoanh"
//     if (fopen(ko".inp", "r")) { 
//         freopen(ko".inp", "r", stdin); 
//         freopen(ko".out", "w", stdout);
//     }
//     // vector <int> res = simulateCollapse(4, {1, 1, 1, 1}, {1, 2, 3, 2}, {2, 3, 4, 4}, {2, 0}, {3, 3});
//     // for (int &v : res) cout << v << " ";
//     init();
//     process();
//     return 0;
// }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35