oj.uz

Submission #403277

# Submission time Handle Problem Language Result Execution time Memory
403277 2021-05-13T01:32:39 Z abdzag Inside information (BOI21_servers) C++17
2.5 / 100
 354 ms 88872 KB 
#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
#define  sz(a) a.size()
typedef long double ld;
using namespace std;
const long long inf = 1e15;
typedef long long ll;
typedef unsigned long long ull;
vector<ll> lis(2e5);
vector<ll> lds(2e5);
vector<ll> ris(2e5);
vector<ll> rds(2e5);
void Uinitate(vector<ll>& p) {
	rep(i, 0, p.size())p[i] = i;
}
ll UfindSet(ll cur, vector<ll>& p) {
	if (p[cur] == cur)return cur;
	return p[cur] = UfindSet(p[cur], p);
}
void Ujoin(ll i, ll j, vector<ll>& p, vector<ll>& r) {
	ll si = UfindSet(i, p);
	ll sj = UfindSet(j, p);
	if (si == sj)return;
	if (r[si] > r[sj])swap(sj, si);
	p[si] = sj;
	r[sj]++;
}
vector<ll> depth(2e5, -1);
pair<pair<ll, ll>, ll> lca(ll a, ll b, vector<vector<pair<ll, ll>>>& parents) {
	bool swaped = depth[a] < depth[b];
	if (depth[a] < depth[b])swap(a, b);
	ll diff = depth[a] - depth[b];
	if (diff % 2 == 0 && diff) {
		a = parents[0][a].first;
		diff--;
	}
	ll mx = 0;
	rrep(i, 19, -1) {
		if (diff & (1 << i)) {
			mx = max(mx, parents[i][a].second);
			if (parents[i][a].first == b) {
				return make_pair(make_pair(a, a), mx);
			}
			a = parents[i][a].first;
		}
	}
	rrep(i, 19, -1) {
		if (parents[i][b] != parents[i][b]) {
			a = parents[i][a].first;
			b = parents[i][b].first;
			mx = max(mx, parents[i][a].second);
			mx = max(mx, parents[i][b].second);
		}
	}
	if (swaped)swap(a, b);
	return make_pair(make_pair(a, b), mx);
}
int main() {
	cin.sync_with_stdio(false);
	ll n, Q;
	cin >> n >> Q;
	vector<vector<pair<ll, ll>>> g(n + 1);
	vector<bitset<5000>> v(n + 1);
	rep(i, 1, n + 1)v[i][i] = 1;
	ll counter = 0;
	rep(i, 0, n + Q - 1) {
		char c;
		ll a, b;
		cin >> c;
		if (c == 'S') {
			cin >> a >> b;
			v[a] |= v[b];
			v[b] |= v[a];
		}
		else if (c == 'Q') {
			cin >> a >> b;
			cout << (v[a][b] ? "yes\n" : "no\n");
		}
		else {
			cin >> a;
		}
	}

	return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:69:5: warning: unused variable 'counter' [-Wunused-variable]
   69 |  ll counter = 0;
      |     ^~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 212 ms 8416 KB Output is correct
2 Correct 220 ms 12496 KB Output is correct
3 Correct 236 ms 12440 KB Output is correct
4 Correct 224 ms 12436 KB Output is correct
5 Correct 255 ms 12392 KB Output is correct
6 Correct 225 ms 12444 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 212 ms 8416 KB Output is correct
2 Correct 220 ms 12496 KB Output is correct
3 Correct 236 ms 12440 KB Output is correct
4 Correct 224 ms 12436 KB Output is correct
5 Correct 255 ms 12392 KB Output is correct
6 Correct 225 ms 12444 KB Output is correct
7 Incorrect 200 ms 8564 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 210 ms 8476 KB Output is correct
2 Runtime error 332 ms 85712 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 210 ms 8476 KB Output is correct
2 Runtime error 332 ms 85712 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 8492 KB Output is correct
2 Runtime error 346 ms 88796 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 8492 KB Output is correct
2 Runtime error 346 ms 88796 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 8572 KB Output is correct
2 Runtime error 337 ms 88804 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 8572 KB Output is correct
2 Runtime error 337 ms 88804 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 215 ms 8436 KB Output is correct
2 Runtime error 354 ms 88872 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 215 ms 8436 KB Output is correct
2 Runtime error 354 ms 88872 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 213 ms 8592 KB Output is correct
2 Correct 227 ms 12344 KB Output is correct
3 Correct 226 ms 12440 KB Output is correct
4 Correct 223 ms 12464 KB Output is correct
5 Correct 222 ms 12380 KB Output is correct
6 Correct 220 ms 12420 KB Output is correct
7 Correct 215 ms 9452 KB Output is correct
8 Runtime error 331 ms 88404 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 213 ms 8592 KB Output is correct
2 Correct 227 ms 12344 KB Output is correct
3 Correct 226 ms 12440 KB Output is correct
4 Correct 223 ms 12464 KB Output is correct
5 Correct 222 ms 12380 KB Output is correct
6 Correct 220 ms 12420 KB Output is correct
7 Correct 215 ms 9452 KB Output is correct
8 Runtime error 331 ms 88404 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -