oj.uz

Submission #552042

# Submission time Handle Problem Language Result Execution time Memory
552042 2022-04-22T09:18:37 Z CpDark Inside information (BOI21_servers) C++17
5 / 100
 909 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;
vector<bitset<SIZE>> bsets;


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 161 ms 1372 KB Output is correct
2 Correct 220 ms 59592 KB Output is correct
3 Correct 225 ms 59884 KB Output is correct
4 Correct 218 ms 59800 KB Output is correct
5 Correct 218 ms 59632 KB Output is correct
6 Correct 205 ms 59660 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 161 ms 1372 KB Output is correct
2 Correct 220 ms 59592 KB Output is correct
3 Correct 225 ms 59884 KB Output is correct
4 Correct 218 ms 59800 KB Output is correct
5 Correct 218 ms 59632 KB Output is correct
6 Correct 205 ms 59660 KB Output is correct
7 Correct 158 ms 1308 KB Output is correct
8 Correct 227 ms 60660 KB Output is correct
9 Correct 350 ms 60876 KB Output is correct
10 Correct 213 ms 60660 KB Output is correct
11 Correct 211 ms 60660 KB Output is correct
12 Correct 909 ms 60844 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 155 ms 1396 KB Output is correct
2 Runtime error 190 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 155 ms 1396 KB Output is correct
2 Runtime error 190 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 161 ms 1356 KB Output is correct
2 Runtime error 192 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 161 ms 1356 KB Output is correct
2 Runtime error 192 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 158 ms 1440 KB Output is correct
2 Runtime error 191 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 158 ms 1440 KB Output is correct
2 Runtime error 191 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 158 ms 1312 KB Output is correct
2 Runtime error 188 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 158 ms 1312 KB Output is correct
2 Runtime error 188 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 158 ms 1400 KB Output is correct
2 Correct 213 ms 59656 KB Output is correct
3 Correct 207 ms 59724 KB Output is correct
4 Correct 212 ms 59812 KB Output is correct
5 Correct 209 ms 59596 KB Output is correct
6 Correct 213 ms 59804 KB Output is correct
7 Correct 168 ms 1444 KB Output is correct
8 Runtime error 191 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 158 ms 1400 KB Output is correct
2 Correct 213 ms 59656 KB Output is correct
3 Correct 207 ms 59724 KB Output is correct
4 Correct 212 ms 59812 KB Output is correct
5 Correct 209 ms 59596 KB Output is correct
6 Correct 213 ms 59804 KB Output is correct
7 Correct 168 ms 1444 KB Output is correct
8 Runtime error 191 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -