oj.uz

Submission #575982

# Submission time Handle Problem Language Result Execution time Memory
575982 2022-06-12T01:41:30 Z jiahng Inside information (BOI21_servers) C++14
50 / 100
 349 ms 113508 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//~ #define ll int
#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 120001
#define INF 1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int N,K;
vpi adj[maxn];
int sz[maxn], lvl[maxn],par[maxn][30];
void find_sz(int x, int p){
	sz[x] = 1;
	aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1){
		find_sz(i.f,x); sz[x] += sz[i.f];
	}
}
int find_cent(int x,int p, int m){
	aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1 && sz[i.f] > m / 2) return find_cent(i.f,x,m);
	return x;
}

bool inc[maxn][30], _dec[maxn][30];
int fi[maxn][30], la[maxn][30]; // All are measured top-down
void find_vals(int x, int p, int d, int incv, int decv, int first_edge, int last_edge){
	inc[x][d] = (incv != -1);
	_dec[x][d] = (decv != -1);
	fi[x][d] = first_edge;
	la[x][d] = last_edge;
	aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1){
		int nincv, ndecv, nfirst_edge;
		if (incv == -1 || i.s < incv) nincv = -1;
		else nincv = i.s;
		
		if (decv == -1 || i.s > decv) ndecv = -1;
		else ndecv = i.s;
		
		if (first_edge == -1) nfirst_edge = i.s;
		else nfirst_edge = first_edge;
		
		find_vals(i.f, x, d, nincv, ndecv, nfirst_edge, i.s); 
	}
}
void decomp(int x,int p,int d){
	find_sz(x, -1);
	int cent = find_cent(x, -1, sz[x]);
	lvl[cent] = d;
	//~ cout << p << ' ' << cent << '\n';
	par[cent][d] = cent;
	FOR(i,0,d-1) par[cent][i] = par[p][i];
	
	find_vals(cent, -1, d, 0, N+1, -1, -1);
	
	aFOR(i,adj[cent]) if (lvl[i.f] == -1) decomp(i.f,cent, d+1);
}

char ch;
int a,b;
int32_t main(){
    fast;
    cin >> N >> K;
    int co = 1;
    
    vector <pii> queries;
    
    FOR(i,1,N+K-1){
		cin >> ch;
		
		if (ch == 'S'){
			cin >> a >> b;
			adj[a].pb(pi(b, co)); adj[b].pb(pi(a,co));
			co++;
		}else if (ch == 'Q'){
			cin >> a >> b;
			queries.pb(pii(pi(a,b), co-1));
		}else{
			cin >> a;
			queries.pb(pii(pi(a, -1), co-1));
		}
	}
	mem(lvl, -1);
	mem(par, -1);
	decomp(1,-1,0);
	//~ cout << la
	//~ return 0;
	//~ FOR(i,1,N) cout << lvl[i] << ' ';
	//~ cout << '\n';
	//~ FOR(i,1,N) cout << par[i][lvl[i]]-1 << ' ';
	//~ cout << '\n';
	//~ cout  << la[5][0];
	//~ return 0;
	aFOR(i,queries){
		if (i.f.s != -1){
			int x = i.f.s, y = i.f.f;
			if (x == y){
				cout << "yes\n"; continue;
			}
			int lca = 0;
			DEC(d,29,0) if (par[x][d] != -1 && par[x][d] == par[y][d]){
				lca = d;
				break;
			}
			//~ cout << lca << ' ';
			if (_dec[x][lca] && inc[y][lca]){
				if (fi[x][lca] == -1 || fi[y][lca] == -1 || 
					fi[x][lca] < fi[y][lca]){
					
					int last = max(fi[x][lca], la[y][lca]);
					if (last <= i.s){
						cout << "yes\n"; continue;
					}
				}
			}
			cout << "no\n";
			
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34624 KB Output is correct
2 Correct 53 ms 36808 KB Output is correct
3 Correct 55 ms 38352 KB Output is correct
4 Correct 46 ms 38236 KB Output is correct
5 Correct 46 ms 38456 KB Output is correct
6 Correct 41 ms 38196 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34624 KB Output is correct
2 Correct 53 ms 36808 KB Output is correct
3 Correct 55 ms 38352 KB Output is correct
4 Correct 46 ms 38236 KB Output is correct
5 Correct 46 ms 38456 KB Output is correct
6 Correct 41 ms 38196 KB Output is correct
7 Incorrect 37 ms 35452 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34656 KB Output is correct
2 Correct 160 ms 103592 KB Output is correct
3 Correct 143 ms 103504 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34656 KB Output is correct
2 Correct 160 ms 103592 KB Output is correct
3 Correct 143 ms 103504 KB Output is correct
4 Incorrect 35 ms 34592 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 34624 KB Output is correct
2 Correct 273 ms 113404 KB Output is correct
3 Correct 291 ms 113464 KB Output is correct
4 Correct 189 ms 113384 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 34624 KB Output is correct
2 Correct 273 ms 113404 KB Output is correct
3 Correct 291 ms 113464 KB Output is correct
4 Correct 189 ms 113384 KB Output is correct
5 Incorrect 40 ms 35520 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 34644 KB Output is correct
2 Correct 179 ms 106732 KB Output is correct
3 Correct 238 ms 107284 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 34644 KB Output is correct
2 Correct 179 ms 106732 KB Output is correct
3 Correct 238 ms 107284 KB Output is correct
4 Incorrect 37 ms 35520 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 34628 KB Output is correct
2 Correct 270 ms 113440 KB Output is correct
3 Correct 279 ms 113460 KB Output is correct
4 Correct 196 ms 113312 KB Output is correct
5 Correct 36 ms 35528 KB Output is correct
6 Correct 183 ms 106860 KB Output is correct
7 Correct 257 ms 107244 KB Output is correct
8 Correct 271 ms 107756 KB Output is correct
9 Correct 281 ms 107648 KB Output is correct
10 Correct 281 ms 111636 KB Output is correct
11 Correct 304 ms 111564 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 34628 KB Output is correct
2 Correct 270 ms 113440 KB Output is correct
3 Correct 279 ms 113460 KB Output is correct
4 Correct 196 ms 113312 KB Output is correct
5 Correct 36 ms 35528 KB Output is correct
6 Correct 183 ms 106860 KB Output is correct
7 Correct 257 ms 107244 KB Output is correct
8 Correct 271 ms 107756 KB Output is correct
9 Correct 281 ms 107648 KB Output is correct
10 Correct 281 ms 111636 KB Output is correct
11 Correct 304 ms 111564 KB Output is correct
12 Incorrect 44 ms 35540 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34660 KB Output is correct
2 Correct 48 ms 36756 KB Output is correct
3 Correct 49 ms 38364 KB Output is correct
4 Correct 45 ms 38260 KB Output is correct
5 Correct 52 ms 38488 KB Output is correct
6 Correct 44 ms 38224 KB Output is correct
7 Correct 36 ms 35564 KB Output is correct
8 Correct 147 ms 106416 KB Output is correct
9 Correct 170 ms 106384 KB Output is correct
10 Correct 40 ms 35480 KB Output is correct
11 Correct 257 ms 113464 KB Output is correct
12 Correct 311 ms 113508 KB Output is correct
13 Correct 181 ms 113384 KB Output is correct
14 Correct 35 ms 35552 KB Output is correct
15 Correct 181 ms 106808 KB Output is correct
16 Correct 261 ms 107388 KB Output is correct
17 Correct 264 ms 107708 KB Output is correct
18 Correct 276 ms 107704 KB Output is correct
19 Correct 289 ms 111544 KB Output is correct
20 Correct 298 ms 111488 KB Output is correct
21 Correct 157 ms 106960 KB Output is correct
22 Correct 205 ms 107060 KB Output is correct
23 Correct 208 ms 107240 KB Output is correct
24 Correct 206 ms 107304 KB Output is correct
25 Correct 349 ms 112036 KB Output is correct
26 Correct 265 ms 106872 KB Output is correct
27 Correct 255 ms 106936 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34660 KB Output is correct
2 Correct 48 ms 36756 KB Output is correct
3 Correct 49 ms 38364 KB Output is correct
4 Correct 45 ms 38260 KB Output is correct
5 Correct 52 ms 38488 KB Output is correct
6 Correct 44 ms 38224 KB Output is correct
7 Correct 36 ms 35564 KB Output is correct
8 Correct 147 ms 106416 KB Output is correct
9 Correct 170 ms 106384 KB Output is correct
10 Correct 40 ms 35480 KB Output is correct
11 Correct 257 ms 113464 KB Output is correct
12 Correct 311 ms 113508 KB Output is correct
13 Correct 181 ms 113384 KB Output is correct
14 Correct 35 ms 35552 KB Output is correct
15 Correct 181 ms 106808 KB Output is correct
16 Correct 261 ms 107388 KB Output is correct
17 Correct 264 ms 107708 KB Output is correct
18 Correct 276 ms 107704 KB Output is correct
19 Correct 289 ms 111544 KB Output is correct
20 Correct 298 ms 111488 KB Output is correct
21 Correct 157 ms 106960 KB Output is correct
22 Correct 205 ms 107060 KB Output is correct
23 Correct 208 ms 107240 KB Output is correct
24 Correct 206 ms 107304 KB Output is correct
25 Correct 349 ms 112036 KB Output is correct
26 Correct 265 ms 106872 KB Output is correct
27 Correct 255 ms 106936 KB Output is correct
28 Incorrect 35 ms 35520 KB Extra information in the output file
29 Halted 0 ms 0 KB -