oj.uz

Submission #575985

# Submission time Handle Problem Language Result Execution time Memory
575985 2022-06-12T02:21:30 Z jiahng Inside information (BOI21_servers) C++14
50 / 100
 342 ms 110156 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);

	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 = la[y][lca];;
					if (lvl[y] == lca) last = fi[x][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 35 ms 34624 KB Output is correct
2 Correct 44 ms 36824 KB Output is correct
3 Correct 47 ms 36908 KB Output is correct
4 Correct 58 ms 36868 KB Output is correct
5 Correct 49 ms 37052 KB Output is correct
6 Correct 40 ms 36836 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 34624 KB Output is correct
2 Correct 44 ms 36824 KB Output is correct
3 Correct 47 ms 36908 KB Output is correct
4 Correct 58 ms 36868 KB Output is correct
5 Correct 49 ms 37052 KB Output is correct
6 Correct 40 ms 36836 KB Output is correct
7 Incorrect 34 ms 34652 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 35 ms 34740 KB Output is correct
2 Correct 169 ms 103516 KB Output is correct
3 Correct 151 ms 103600 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 34740 KB Output is correct
2 Correct 169 ms 103516 KB Output is correct
3 Correct 151 ms 103600 KB Output is correct
4 Incorrect 34 ms 34628 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 35 ms 34624 KB Output is correct
2 Correct 295 ms 110140 KB Output is correct
3 Correct 263 ms 110136 KB Output is correct
4 Correct 185 ms 110156 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 34624 KB Output is correct
2 Correct 295 ms 110140 KB Output is correct
3 Correct 263 ms 110136 KB Output is correct
4 Correct 185 ms 110156 KB Output is correct
5 Incorrect 34 ms 34676 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 37 ms 34608 KB Output is correct
2 Correct 195 ms 103564 KB Output is correct
3 Correct 240 ms 104068 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34608 KB Output is correct
2 Correct 195 ms 103564 KB Output is correct
3 Correct 240 ms 104068 KB Output is correct
4 Incorrect 33 ms 34656 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 37 ms 34616 KB Output is correct
2 Correct 291 ms 110120 KB Output is correct
3 Correct 265 ms 110128 KB Output is correct
4 Correct 174 ms 110104 KB Output is correct
5 Correct 37 ms 34768 KB Output is correct
6 Correct 179 ms 103684 KB Output is correct
7 Correct 229 ms 104056 KB Output is correct
8 Correct 275 ms 104384 KB Output is correct
9 Correct 298 ms 104556 KB Output is correct
10 Correct 290 ms 108244 KB Output is correct
11 Correct 336 ms 108272 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34616 KB Output is correct
2 Correct 291 ms 110120 KB Output is correct
3 Correct 265 ms 110128 KB Output is correct
4 Correct 174 ms 110104 KB Output is correct
5 Correct 37 ms 34768 KB Output is correct
6 Correct 179 ms 103684 KB Output is correct
7 Correct 229 ms 104056 KB Output is correct
8 Correct 275 ms 104384 KB Output is correct
9 Correct 298 ms 104556 KB Output is correct
10 Correct 290 ms 108244 KB Output is correct
11 Correct 336 ms 108272 KB Output is correct
12 Incorrect 35 ms 34628 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 34 ms 34588 KB Output is correct
2 Correct 45 ms 36812 KB Output is correct
3 Correct 56 ms 37040 KB Output is correct
4 Correct 49 ms 36940 KB Output is correct
5 Correct 47 ms 37052 KB Output is correct
6 Correct 45 ms 36804 KB Output is correct
7 Correct 36 ms 34620 KB Output is correct
8 Correct 165 ms 103600 KB Output is correct
9 Correct 152 ms 103548 KB Output is correct
10 Correct 34 ms 34628 KB Output is correct
11 Correct 257 ms 110128 KB Output is correct
12 Correct 337 ms 110144 KB Output is correct
13 Correct 177 ms 110136 KB Output is correct
14 Correct 34 ms 34636 KB Output is correct
15 Correct 181 ms 103540 KB Output is correct
16 Correct 279 ms 103964 KB Output is correct
17 Correct 301 ms 104328 KB Output is correct
18 Correct 270 ms 104464 KB Output is correct
19 Correct 288 ms 108208 KB Output is correct
20 Correct 298 ms 108252 KB Output is correct
21 Correct 157 ms 103540 KB Output is correct
22 Correct 160 ms 103660 KB Output is correct
23 Correct 209 ms 103992 KB Output is correct
24 Correct 211 ms 103992 KB Output is correct
25 Correct 342 ms 108732 KB Output is correct
26 Correct 268 ms 103480 KB Output is correct
27 Correct 266 ms 103436 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 34588 KB Output is correct
2 Correct 45 ms 36812 KB Output is correct
3 Correct 56 ms 37040 KB Output is correct
4 Correct 49 ms 36940 KB Output is correct
5 Correct 47 ms 37052 KB Output is correct
6 Correct 45 ms 36804 KB Output is correct
7 Correct 36 ms 34620 KB Output is correct
8 Correct 165 ms 103600 KB Output is correct
9 Correct 152 ms 103548 KB Output is correct
10 Correct 34 ms 34628 KB Output is correct
11 Correct 257 ms 110128 KB Output is correct
12 Correct 337 ms 110144 KB Output is correct
13 Correct 177 ms 110136 KB Output is correct
14 Correct 34 ms 34636 KB Output is correct
15 Correct 181 ms 103540 KB Output is correct
16 Correct 279 ms 103964 KB Output is correct
17 Correct 301 ms 104328 KB Output is correct
18 Correct 270 ms 104464 KB Output is correct
19 Correct 288 ms 108208 KB Output is correct
20 Correct 298 ms 108252 KB Output is correct
21 Correct 157 ms 103540 KB Output is correct
22 Correct 160 ms 103660 KB Output is correct
23 Correct 209 ms 103992 KB Output is correct
24 Correct 211 ms 103992 KB Output is correct
25 Correct 342 ms 108732 KB Output is correct
26 Correct 268 ms 103480 KB Output is correct
27 Correct 266 ms 103436 KB Output is correct
28 Incorrect 38 ms 34632 KB Extra information in the output file
29 Halted 0 ms 0 KB -