제출 #557942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557942		AdamGS	Inside information (BOI21_servers)	C++17	2.50 / 100	100 ms	21988 KiB

servers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=12e4+7, INF=1e9+7;
vector<pair<int,int>>V[LIM];
vector<int>S;
int typ[LIM], A[LIM], B[LIM], czas[LIM], usun[LIM], ile[LIM], ans[LIM];
int rosnie[LIM], maleje[LIM], najw[LIM], najm[LIM], oc[LIM], ktory[LIM];
int cent(int x, int o, int n) {
	S.pb(x);
	ile[x]=1;
	int p=-1, ma=0;
	for(auto i : V[x]) if(!usun[i.nd] && i.nd!=o) {
		int t=cent(i.nd, x, n);
		if(t!=-1) p=t;
		ile[x]+=ile[i.nd];
		ma=max(ma, ile[i.nd]);
	}
	ma=max(ma, n-ile[x]);
	if(ma<=n/2) p=x;
	return p;
}
void DFS(int x, int o, int lst) {
	for(auto i : V[x]) if(!usun[i.nd] && i.nd!=o) {
		oc[i.nd]=oc[x];
		rosnie[i.nd]=rosnie[x];
		maleje[i.nd]=maleje[x];
		najw[i.nd]=najw[x];
		najm[i.nd]=najm[x];
		if(lst && i.st<lst) rosnie[i.nd]=0;
		if(lst && i.st>lst) maleje[i.nd]=0;
		if(lst) {
			najw[i.nd]=max(najw[i.nd], i.st);
			najm[i.nd]=min(najm[i.nd], i.st);
		}
		DFS(i.nd, x, i.st);
	}
}
void cd(int x, int n, vector<int>pyt) {
	S.clear();
	x=cent(x, x, n);
	cent(x, x, n);
	usun[x]=rosnie[x]=maleje[x]=1;
	najm[x]=INF;
	najw[x]=-INF;
	rep(i, V[x].size()) if(!usun[V[x][i].nd]) {
		ktory[V[x][i].nd]=i;
		oc[V[x][i].nd]=V[x][i].nd;
		rosnie[V[x][i].nd]=maleje[V[x][i].nd]=1;
		najw[V[x][i].nd]=najm[V[x][i].nd]=V[x][i].st;
		DFS(V[x][i].nd, x, V[x][i].st);
	}
	vector<int>P[V[x].size()], Q, C;
	for(auto i : pyt) {
		if(typ[i]) {
			C.pb(i);
			if(A[i]!=x) P[ktory[oc[A[i]]]].pb(i);
		} else {
			if(oc[A[i]]==oc[B[i]] && A[i]!=x) P[ktory[oc[A[i]]]].pb(i);
			else Q.pb(i);
		}
	}
	for(auto i : Q) {
		if(A[i]==x && maleje[B[i]] && najw[B[i]]<=czas[i]) ans[i]=1;
		if(B[i]==x && rosnie[A[i]] && najw[A[i]]<=czas[i]) ans[i]=1;
		if(rosnie[A[i]] && maleje[B[i]] && najm[A[i]]>najw[B[i]]) 
			if(max(najw[A[i]], najw[B[i]])<=czas[i]) ans[i]=1;
	}
	rep(i, V[x].size()) if(!usun[V[x][i].nd]) cd(V[x][i].nd, ile[V[x][i].nd], P[i]);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k, ilen=0, ilek=0;
	cin >> n >> k;
	rep(i, n+k-1) {
		char c;
		cin >> c;
		if(c=='S') {
			++ilen;
			int a, b;
			cin >> a >> b; --a; --b;
			V[a].pb({ilen, b});
			V[b].pb({ilen, a});
		} else if(c=='Q') {
			cin >> A[ilek] >> B[ilek]; 
			--A[ilek]; --B[ilek]; czas[ilek]=ilen;
			++ilek;
		} else {
			cin >> A[ilek]; --A[ilek];
			czas[ilek]=ilen; typ[ilek]=1;
			++ilek;
		}
	}
	rep(i, n) sort(all(V[i]));
	vector<int>T;
	rep(i, k) T.pb(i);
	cd(0, n, T);
	rep(i, k) if(typ[i]) cout << ans[i] << '\n'; else cout << (ans[i]?"yes":"no") << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'void cd(int, int, std::vector<int>)':
servers.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
servers.cpp:52:2: note: in expansion of macro 'rep'
   52 |  rep(i, V[x].size()) if(!usun[V[x][i].nd]) {
      |  ^~~
servers.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
servers.cpp:75:2: note: in expansion of macro 'rep'
   75 |  rep(i, V[x].size()) if(!usun[V[x][i].nd]) cd(V[x][i].nd, ile[V[x][i].nd], P[i]);
      |  ^~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5