oj.uz

답안 #898951

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898951 2024-01-05T09:51:21 Z arashMLG Inside information (BOI21_servers) C++17
2.5 / 100
 75 ms 16316 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);
	for(int i = 0 ;i < h[v] - h[u]; 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
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 7636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 7636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 7632 KB Output is correct
2 Correct 59 ms 16220 KB Output is correct
3 Correct 59 ms 16316 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 7632 KB Output is correct
2 Correct 59 ms 16220 KB Output is correct
3 Correct 59 ms 16316 KB Output is correct
4 Runtime error 5 ms 9048 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 7608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 7608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 7664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 7664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 7592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 7592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 7620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 7620 KB Output isn't correct
2 Halted 0 ms 0 KB -