oj.uz

Submission #552047

# Submission time Handle Problem Language Result Execution time Memory
552047 2022-04-22T09:58:39 Z CpDark Inside information (BOI21_servers) C++14
5 / 100
 921 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
const int inf = 1e9 + 7;


struct DSU {
	vi par;
	vi subSize;
	vector<set<int>> data;

	void init(int n) {
		par.resize(n + 1);
		subSize.resize(n + 1);
		data.resize(n + 1);
		for (int i = 1; i <= n; i++) {
			par[i] = i;
			subSize[i] = 1;
			data[i].insert(i);
		}
	}

	int findSet(int v) {
		if (v == par[v]) return v;
		return findSet(par[v]);
	}


	bool unite(int v, int u) {
		int pv = findSet(v);
		int pu = findSet(u);
		if (pv == pu)return false;

		if (subSize[pv] > subSize[pu]) swap(pv, pu);
		par[pv] = pu;
		subSize[pu] += subSize[pv];


		bool swaped = false;
		if (data[pv].size() > data[pu].size()) {
			swap(pv, pu);
			swaped = true;
		}

		auto it = data[pv].begin();
		for (int i = 0; i < data[pv].size(); i++) {
			data[pu].insert(*it);
			it++;
		}

		if (swaped) {
			swap(data[pv], data[pu]);
		}

		return true;
	}


	bool query(int v, int d) {
		int pv = findSet(v);

		auto it = data[pv].find(d);
		if (it == data[pv].end()) return false;
		return true;
	}

	int count(int d) {
		int pv = findSet(d);
		int ans = subSize[pv];
		return ans;
	}
};

vvp graph;
const int SIZE = 120002;
bitset<SIZE>bsets[SIZE];


void unite(int v, int u) {
	bsets[v] = bsets[v] | bsets[u];
	bsets[u] = bsets[u] | bsets[v];
}

bool dfsfind(int v, int p, int lasttime, int x) {
	if (v == x)return true;

	for (int i = 0; i < graph[v].size(); i++) {
		int u = graph[v][i].first;
		int time = graph[v][i].second;
		if (u != p && time < lasttime) {
			bool curr = dfsfind(u, v, time, x);
			if (curr)return true;
		}
	}
	return false;
}

int dfscount(int v, int p, int lasttime) {
	int sum = 1;

	for (int i = 0; i < graph[v].size(); i++) {
		int u = graph[v][i].first;
		int time = graph[v][i].second;
		if (u != p && time > lasttime) {
			int curr = dfscount(u, v, time);
			sum += curr;
		}
	}
	return sum;
}

void solve() {
	int n, k;
	cin >> n >> k;
	graph.resize(n + 1);
	//bsets.resize(n + 1);

	for (int i = 1; i <= n; i++) {
		bsets[i][i] = true;
	}
	//DSU dsu;
	//dsu.init(n);
	char t;
	int a, b;
	int maxtime = n + 3;
	int timer = 0;
	for (int i = 0; i < n + k - 1; i++) {
		cin >> t;
		if (t == 'S') {
			cin >> a >> b;
			unite(a, b);
			graph[a].push_back({ b,timer });
			graph[b].push_back({ a,timer });
			timer++;
			//dsu.unite(a, b);
		}
		if (t == 'Q') {
			cin >> a >> b;
			//bool ans = dfsfind(a, a, maxtime, b);
			bool ans = bsets[a][b];
			//bool ans = dsu.query(a, b);
			if (ans) {
				cout << "yes" << endl;
			}
			else {
				cout << "no" << endl;
			}
		}
		if (t == 'C') {
			cin >> a;
			int ans = dfscount(a, a, -1);
			//int ans = dsu.count(a);
			//int ans = 0;
			cout << ans << endl;
		}
	}

}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();

	return 0;
}

Compilation message

servers.cpp: In member function 'bool DSU::unite(int, int)':
servers.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int i = 0; i < data[pv].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'bool dfsfind(int, int, int, int)':
servers.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i = 0; i < graph[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'int dfscount(int, int, int)':
servers.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for (int i = 0; i < graph[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'void solve()':
servers.cpp:135:6: warning: unused variable 'maxtime' [-Wunused-variable]
  135 |  int maxtime = n + 3;
      |      ^~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 169 ms 1420 KB Output is correct
2 Correct 223 ms 59736 KB Output is correct
3 Correct 224 ms 59696 KB Output is correct
4 Correct 237 ms 59624 KB Output is correct
5 Correct 259 ms 59572 KB Output is correct
6 Correct 233 ms 59736 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 169 ms 1420 KB Output is correct
2 Correct 223 ms 59736 KB Output is correct
3 Correct 224 ms 59696 KB Output is correct
4 Correct 237 ms 59624 KB Output is correct
5 Correct 259 ms 59572 KB Output is correct
6 Correct 233 ms 59736 KB Output is correct
7 Correct 178 ms 1356 KB Output is correct
8 Correct 231 ms 59612 KB Output is correct
9 Correct 376 ms 59720 KB Output is correct
10 Correct 218 ms 59568 KB Output is correct
11 Correct 254 ms 59552 KB Output is correct
12 Correct 921 ms 59720 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 162 ms 1328 KB Output is correct
2 Runtime error 298 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 162 ms 1328 KB Output is correct
2 Runtime error 298 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 1484 KB Output is correct
2 Runtime error 243 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 1484 KB Output is correct
2 Runtime error 243 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 1412 KB Output is correct
2 Runtime error 226 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 1412 KB Output is correct
2 Runtime error 226 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 177 ms 1500 KB Output is correct
2 Runtime error 198 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 177 ms 1500 KB Output is correct
2 Runtime error 198 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 160 ms 1484 KB Output is correct
2 Correct 268 ms 59684 KB Output is correct
3 Correct 210 ms 59852 KB Output is correct
4 Correct 252 ms 59732 KB Output is correct
5 Correct 221 ms 59748 KB Output is correct
6 Correct 235 ms 59800 KB Output is correct
7 Correct 172 ms 1484 KB Output is correct
8 Runtime error 225 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 160 ms 1484 KB Output is correct
2 Correct 268 ms 59684 KB Output is correct
3 Correct 210 ms 59852 KB Output is correct
4 Correct 252 ms 59732 KB Output is correct
5 Correct 221 ms 59748 KB Output is correct
6 Correct 235 ms 59800 KB Output is correct
7 Correct 172 ms 1484 KB Output is correct
8 Runtime error 225 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -