oj.uz

답안 #534401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534401 2022-03-08T06:36:21 Z NhatMinh0208 Inside information (BOI21_servers) C++14
50 / 100
 192 ms 52424 KB 
#ifndef CPL_TEMPLATE
#define CPL_TEMPLATE
/*
	Normie's Template v2.5
	Changes:
    Added warning against using pragmas on USACO.
*/
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;
 
//Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.)
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
 
// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
// template<typename T>
// __attribute__((always_inline)) void chkmin(T& a, const T& b) {
//     a=(a<b)?a:b;
// }
 
// template<typename T>
// __attribute__((always_inline)) void chkmax(T& a, const T& b) {
//     a=(a>b)?a:b;
// }
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;
 
// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
	if (!x) return 1;
	ll res=BOW(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2) res*=a;
	return res%p;
}
ll INV(ll a, ll p)
{
	return BOW(a,p-2,p);
}
//---------END-------//
#endif
vector<pii(int)> gt[120001];
int n,m,i,j,k,t,t1,u,v,a,b;
int qt[240001];
int qx[240001];
int qy[240001];
int inc[120001][20];
int de[120001][20];
int jmp[120001][20];
pii(int) par[120001];
int dep[120001];
void init(int x, pii(int) p) {
	par[x]=p;
	dep[x]=dep[p.fi]+1;
	jmp[x][0]=p.fi;
	inc[x][0]=p.se;
	de[x][0]=p.se;
	int u;
	for (int i=1;i<20;i++) {
		u=jmp[x][i-1];
		jmp[x][i]=jmp[u][i-1];
		if (inc[x][i-1]==-1 || inc[u][i-1]==-1 || inc[x][i-1]>par[u].se) inc[x][i]=-1;
		else inc[x][i]=inc[u][i-1];
 
		if (de[x][i-1]==-1 || de[u][i-1]==-1 || de[x][i-1]<par[u].se) de[x][i]=-1;
		else de[x][i]=de[u][i-1];
		// cout<<x<<' '<<i<<' '<<jmp[x][i]<<' '<<de[x][i]<<' '<<inc[x][i]<<endl;
	}
	for (auto g : gt[x]) if (g.fi-p.fi) init(g.fi, {x,g.se});
}
 
int chk(int u, int v) {
	if (u==v) return 0;
	int cu=u,cv=v;
	int lu=-1e9,lv=1e9;
	for (int i=19;i>=0;i--) {
		if (dep[cu]-dep[cv]>=(1<<i)) {
			if (inc[cu][i]==-1 || lu>par[cu].se) return -1;
			lu=inc[cu][i];
			cu=jmp[cu][i];
		}
		if (dep[cv]-dep[cu]>=(1<<i)) {
			if (de[cv][i]==-1 || lv<par[cv].se) return -1;
			lv=de[cv][i];
			cv=jmp[cv][i];
		}
	}
	if (cu==cv) {
		if (cu==u) {
			return par[v].se;
		}
		else if (cu==v) {
			return lu;
		}
		else assert(0);
	}
	else {
		for (int i=19;i>=0;i--) if (jmp[cu][i]-jmp[cv][i]) {
			{
				if (inc[cu][i]==-1 || lu>par[cu].se) return -1;
				lu=inc[cu][i];
				cu=jmp[cu][i];
			}
			{
				if (de[cv][i]==-1 || lv<par[cv].se) return -1;
				lv=de[cv][i];
				cv=jmp[cv][i];
			}
		}
		if (lu<=par[cu].se && par[cu].se<=par[cv].se && par[cv].se<=lv) return par[v].se;
		else return -1;
	}
}
 
int main()
{
	fio;
	cin>>n>>m;
	char c;
	for (i=0;i<n+m-1;i++) {
		cin>>c;
		if (c=='S') {
			t++;
			qt[i]=t;
			cin>>qx[i]>>qy[i];
			// cout<<qx[i]<<' '<<qy[i]<<' '<<qt[i]<<endl;
			gt[qx[i]].push_back({qy[i],t});
			gt[qy[i]].push_back({qx[i],t});
		}
		else if (c=='Q') {
			qt[i]=-t;
			cin>>qx[i]>>qy[i];
		}
		else if (c=='C') {
			// return 0;
			qt[i]=-t;
			cin>>qx[i];
		}
	}
	init(1,{1,0});
	for (i=0;i<n+m-1;i++) if (qt[i]<=0) {
		a = chk(qy[i],qx[i]);
		if (a==-1 || a>(-qt[i])) cout<<"no\n";
		else cout<<"yes\n";
	}
}
// a;

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 4932 KB Output is correct
2 Correct 37 ms 7496 KB Output is correct
3 Correct 35 ms 7492 KB Output is correct
4 Correct 29 ms 7624 KB Output is correct
5 Correct 31 ms 7748 KB Output is correct
6 Correct 39 ms 7524 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 4932 KB Output is correct
2 Correct 37 ms 7496 KB Output is correct
3 Correct 35 ms 7492 KB Output is correct
4 Correct 29 ms 7624 KB Output is correct
5 Correct 31 ms 7748 KB Output is correct
6 Correct 39 ms 7524 KB Output is correct
7 Incorrect 28 ms 5800 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 4940 KB Output is correct
2 Correct 124 ms 40620 KB Output is correct
3 Correct 130 ms 40596 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 4940 KB Output is correct
2 Correct 124 ms 40620 KB Output is correct
3 Correct 130 ms 40596 KB Output is correct
4 Incorrect 29 ms 4932 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 4896 KB Output is correct
2 Correct 122 ms 49068 KB Output is correct
3 Correct 116 ms 49116 KB Output is correct
4 Correct 124 ms 49076 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 4896 KB Output is correct
2 Correct 122 ms 49068 KB Output is correct
3 Correct 116 ms 49116 KB Output is correct
4 Correct 124 ms 49076 KB Output is correct
5 Incorrect 26 ms 4900 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 4932 KB Output is correct
2 Correct 131 ms 43820 KB Output is correct
3 Correct 168 ms 44296 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 4932 KB Output is correct
2 Correct 131 ms 43820 KB Output is correct
3 Correct 168 ms 44296 KB Output is correct
4 Incorrect 31 ms 5828 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 4944 KB Output is correct
2 Correct 116 ms 49032 KB Output is correct
3 Correct 117 ms 49040 KB Output is correct
4 Correct 177 ms 49048 KB Output is correct
5 Correct 31 ms 4940 KB Output is correct
6 Correct 119 ms 43844 KB Output is correct
7 Correct 138 ms 44356 KB Output is correct
8 Correct 141 ms 44780 KB Output is correct
9 Correct 151 ms 44780 KB Output is correct
10 Correct 192 ms 49224 KB Output is correct
11 Correct 173 ms 48548 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 4944 KB Output is correct
2 Correct 116 ms 49032 KB Output is correct
3 Correct 117 ms 49040 KB Output is correct
4 Correct 177 ms 49048 KB Output is correct
5 Correct 31 ms 4940 KB Output is correct
6 Correct 119 ms 43844 KB Output is correct
7 Correct 138 ms 44356 KB Output is correct
8 Correct 141 ms 44780 KB Output is correct
9 Correct 151 ms 44780 KB Output is correct
10 Correct 192 ms 49224 KB Output is correct
11 Correct 173 ms 48548 KB Output is correct
12 Incorrect 26 ms 5836 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 4932 KB Output is correct
2 Correct 44 ms 7480 KB Output is correct
3 Correct 40 ms 7468 KB Output is correct
4 Correct 30 ms 7600 KB Output is correct
5 Correct 31 ms 7748 KB Output is correct
6 Correct 40 ms 7496 KB Output is correct
7 Correct 31 ms 5744 KB Output is correct
8 Correct 129 ms 43476 KB Output is correct
9 Correct 145 ms 43460 KB Output is correct
10 Correct 24 ms 5828 KB Output is correct
11 Correct 123 ms 52344 KB Output is correct
12 Correct 129 ms 52424 KB Output is correct
13 Correct 155 ms 52296 KB Output is correct
14 Correct 27 ms 5828 KB Output is correct
15 Correct 118 ms 43836 KB Output is correct
16 Correct 155 ms 44276 KB Output is correct
17 Correct 133 ms 44744 KB Output is correct
18 Correct 141 ms 44696 KB Output is correct
19 Correct 182 ms 49316 KB Output is correct
20 Correct 173 ms 48580 KB Output is correct
21 Correct 121 ms 43948 KB Output is correct
22 Correct 134 ms 43952 KB Output is correct
23 Correct 140 ms 44388 KB Output is correct
24 Correct 137 ms 44308 KB Output is correct
25 Correct 148 ms 46088 KB Output is correct
26 Correct 129 ms 43868 KB Output is correct
27 Correct 131 ms 43892 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 4932 KB Output is correct
2 Correct 44 ms 7480 KB Output is correct
3 Correct 40 ms 7468 KB Output is correct
4 Correct 30 ms 7600 KB Output is correct
5 Correct 31 ms 7748 KB Output is correct
6 Correct 40 ms 7496 KB Output is correct
7 Correct 31 ms 5744 KB Output is correct
8 Correct 129 ms 43476 KB Output is correct
9 Correct 145 ms 43460 KB Output is correct
10 Correct 24 ms 5828 KB Output is correct
11 Correct 123 ms 52344 KB Output is correct
12 Correct 129 ms 52424 KB Output is correct
13 Correct 155 ms 52296 KB Output is correct
14 Correct 27 ms 5828 KB Output is correct
15 Correct 118 ms 43836 KB Output is correct
16 Correct 155 ms 44276 KB Output is correct
17 Correct 133 ms 44744 KB Output is correct
18 Correct 141 ms 44696 KB Output is correct
19 Correct 182 ms 49316 KB Output is correct
20 Correct 173 ms 48580 KB Output is correct
21 Correct 121 ms 43948 KB Output is correct
22 Correct 134 ms 43952 KB Output is correct
23 Correct 140 ms 44388 KB Output is correct
24 Correct 137 ms 44308 KB Output is correct
25 Correct 148 ms 46088 KB Output is correct
26 Correct 129 ms 43868 KB Output is correct
27 Correct 131 ms 43892 KB Output is correct
28 Incorrect 28 ms 5700 KB Extra information in the output file
29 Halted 0 ms 0 KB -