oj.uz

Submission #898956

# Submission time Handle Problem Language Result Execution time Memory
898956 2024-01-05T09:59:29 Z arashMLG Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 24504 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 12e4 + 23;
const int LOG = 17;
const ll inf = 1e18;

#define F         first
#define S         second
#define pb        push_back
#define sz(x)     ((int)x.size())
#define all(x)    x.begin(),x.end()
#define lc        (v<<1)
#define rc        ((v<<1)|1)
#define debug(x)  cerr<<#x << " : " << x << endl;

struct query {
	char c;
	int a,b;
	int time;
	query(char C,int A,int B,int TIME) {
		c= C;
		a= A;
		b= B;
		time = TIME;
	}
};

int n,m;
vector<pii> G[N];
vector<query> quer;
int par[N];
int val[N];
int h[N];

void dfsset(int v,int p = -1,int wp=0){ 
	val[v] = wp;
	//debug(v);
	for(auto [u,w] : G[v]) if(u != p) {
		h[u] = h[v] + 1;
		par[u] = v;
		dfsset(u,v,w);
	}
}

int timer= 1;

int lca(int v,int u) {
	if(h[v]< h[u]) swap(v,u);
	int x = h[v]-h[u];
	for(int i = 0 ;i <x; i ++) v = par[v];
	if(v == u) return v;
	while(v != u) {
		v = par[v];
		u = par[u];
	}
	return v;
}

bool check(int a,int b) {
	// a-> b
	if(a == b) return true;
	int l = lca(a,b);
	vector<int> vals1,vals2;
	while(a != l) {
		vals1.pb(val[a]);
		a = par[a];
	}
	while(b != l) {
		vals2.pb(val[b]);
		b = par[b];
	}
	reverse(all(vals2));
	for(int x : vals2) vals1.pb(x);
	return is_sorted(all(vals1)) && vals1.back() <= timer;
}

int32_t main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m; m+= n-1;
	while(timer <= m) {
		char c; cin>>c;
		assert(c != 'C');
		int a,b; cin>>a>>b;
		quer.emplace_back(c,a,b,timer);
		if(c == 'S') {
			G[a].pb({b,timer});
			G[b].pb({a,timer});
		}
		timer ++;
	}
	dfsset(1);
	timer = 1;
	for(auto q : quer) {
		if(q.c == 'S') {
			timer ++;
			continue;
		}
		int a =q.a,b=q.b;
		cout<< (check(b,a) ? "yes" : "no") << '\n';
		timer ++;
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6856 KB Output is correct
2 Correct 56 ms 8124 KB Output is correct
3 Correct 33 ms 8420 KB Output is correct
4 Correct 465 ms 8684 KB Output is correct
5 Correct 761 ms 8380 KB Output is correct
6 Correct 34 ms 8432 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6856 KB Output is correct
2 Correct 56 ms 8124 KB Output is correct
3 Correct 33 ms 8420 KB Output is correct
4 Correct 465 ms 8684 KB Output is correct
5 Correct 761 ms 8380 KB Output is correct
6 Correct 34 ms 8432 KB Output is correct
7 Runtime error 5 ms 9052 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6860 KB Output is correct
2 Correct 57 ms 13756 KB Output is correct
3 Correct 57 ms 13544 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6860 KB Output is correct
2 Correct 57 ms 13756 KB Output is correct
3 Correct 57 ms 13544 KB Output is correct
4 Runtime error 5 ms 9052 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6868 KB Output is correct
2 Correct 75 ms 24500 KB Output is correct
3 Correct 91 ms 24248 KB Output is correct
4 Execution timed out 3546 ms 23976 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6868 KB Output is correct
2 Correct 75 ms 24500 KB Output is correct
3 Correct 91 ms 24248 KB Output is correct
4 Execution timed out 3546 ms 23976 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6860 KB Output is correct
2 Correct 86 ms 16708 KB Output is correct
3 Correct 84 ms 17268 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6860 KB Output is correct
2 Correct 86 ms 16708 KB Output is correct
3 Correct 84 ms 17268 KB Output is correct
4 Runtime error 5 ms 9124 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6860 KB Output is correct
2 Correct 83 ms 24500 KB Output is correct
3 Correct 78 ms 24116 KB Output is correct
4 Execution timed out 3538 ms 23900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6860 KB Output is correct
2 Correct 83 ms 24500 KB Output is correct
3 Correct 78 ms 24116 KB Output is correct
4 Execution timed out 3538 ms 23900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6868 KB Output is correct
2 Correct 59 ms 8212 KB Output is correct
3 Correct 43 ms 8392 KB Output is correct
4 Correct 450 ms 8660 KB Output is correct
5 Correct 772 ms 8636 KB Output is correct
6 Correct 30 ms 8168 KB Output is correct
7 Correct 26 ms 7636 KB Output is correct
8 Correct 60 ms 16284 KB Output is correct
9 Correct 61 ms 16308 KB Output is correct
10 Correct 46 ms 7564 KB Output is correct
11 Correct 78 ms 24504 KB Output is correct
12 Correct 71 ms 24032 KB Output is correct
13 Execution timed out 3517 ms 24080 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6868 KB Output is correct
2 Correct 59 ms 8212 KB Output is correct
3 Correct 43 ms 8392 KB Output is correct
4 Correct 450 ms 8660 KB Output is correct
5 Correct 772 ms 8636 KB Output is correct
6 Correct 30 ms 8168 KB Output is correct
7 Correct 26 ms 7636 KB Output is correct
8 Correct 60 ms 16284 KB Output is correct
9 Correct 61 ms 16308 KB Output is correct
10 Correct 46 ms 7564 KB Output is correct
11 Correct 78 ms 24504 KB Output is correct
12 Correct 71 ms 24032 KB Output is correct
13 Execution timed out 3517 ms 24080 KB Time limit exceeded
14 Halted 0 ms 0 KB -