oj.uz

답안 #898991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898991 2024-01-05T10:35:18 Z arashMLG Inside information (BOI21_servers) C++17
0 / 100
 34 ms 35060 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)

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 up[LOG][N],mx[LOG][N],mn[LOG][N];
bool is[LOG][N],si[LOG][N];
int val[N];
int h[N];

void dfsset(int v,int p = -1,int wp=0){ 
	//if(p != -1) remove(all(G[v]),make_pair(p,wp));
	up[0][v] = (p == -1? v: p);
	mx[0][v] = mn[0][v] = wp;
	is[0][v] = si[0][v] = true;
	for(int i = 1; i < LOG; i ++) {
		up[i][v] = up[i-1][up[i-1][v]];
		mx[i][v] = max(mx[i-1][v],mx[i-1][up[i-1][v]]);
		mn[i][v] = min(mn[i-1][v],mn[i-1][up[i-1][v]]);
		is[i][v] = is[i-1][v] && (val[up[i-1][v]] <= mn[i-1][v]) && is[i-1][up[i-1][v]];
		si[i][v] = si[i-1][v] && (val[up[i-1][v]] >= mx[i-1][v]) && si[i-1][up[i-1][v]];
	}
	val[v] = wp;
	for(auto [u,w] : G[v]) if(u != p) {
		h[u] = h[v] + 1;
		dfsset(u,v,w);
	}
}

int timer= 1;

int gmx(int v,int k) {
	int ans=0;
	for(int i =0; i < LOG; i ++) 
		if((k>>i)&1)
			ans= max(ans,mx[i][v]),v= up[i][v];
	return ans;
}

int gp(int v,int k) {
	for(int i = 0 ; i< LOG; i++)
		if((k>>i)&1)
			v = up[i][v];
	return v;
}

int lca(int v,int u) {
	if(h[v]< h[u]) swap(v,u);
	v = gp(v,h[v] -h[u]);
	if(v == u) return v;
	for(int i = LOG-1;i >= 0 ; i --) 
		if(up[i][v] != up[i][u])
			v = up[i][v],u = up[i][u];
	return up[0][v];	
}

bool os(int v,int k) {
	bool ans =true;
	for(int i = 0 ; i< LOG; i++)
		if((k>>i)&1)
			ans &= is[i][v]&& val[v] >= val[up[0][v]],v = up[i][v];
	return ans;
}

bool so(int v,int k) {
	bool ans =true;
	for(int i = 0 ; i< LOG; i++)
		if((k>>i)&1)
			ans &= si[i][v]&&val[v] <= val[up[0][v]],v = up[i][v];
	return ans;
}

bool ok(int a,int b) {
	// a->b
	if(a == b) return true;
	int l = lca(a,b);
	int mx = max(gmx(a,h[a]-h[l]), gmx(b,h[b]-h[l]));
	if(mx > timer) return false;
	if(l == a) {
		return os(b,h[b]-h[a]);
	} else if(l == b) {
		return so(a,h[a]-h[b]);
	} else {
		if(!so(a,h[a]-h[l])) return false;
		if(!os(b,h[b]-h[l])) return false;
		if(val[gp(a,h[a]-h[l]-1)] > val[gp(b,h[b]-h[l]-1)]) return false;
		return true;
	}
}

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

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

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

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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