제출 #557958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557958		AdamGS	Inside information (BOI21_servers)	C++17	100 / 100	627 ms	37192 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) {
	x=cent(x, x, n);
	S.clear();
	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 && B[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;
	}
	vector<pair<int,int>>T;
	for(auto i : S) if(i!=x && rosnie[i]) T.pb({najw[i], -ktory[oc[i]]-1});
	for(auto i : C) if(maleje[A[i]]) {
		if(najw[A[i]]<=czas[i]) ++ans[i];
		T.pb({czas[i], i});
	}
	int N=1;
	while(N<V[x].size()) N*=2;
	vector<int>tr(2*N);
	sort(all(T));
	for(auto i : T) {
		if(i.nd<0) {
			i.nd*=-1; --i.nd;
			i.nd+=N;
			while(i.nd) {
				++tr[i.nd];
				i.nd/=2;
			}
		} else {
			int l=ktory[oc[A[i.nd]]]+1, r=V[x].size()-1;
			if(A[i.nd]==x) l=0;
			if(l>r) continue;
			l+=N; r+=N;
			ans[i.nd]+=tr[l];
			if(l!=r) ans[i.nd]+=tr[r];
			while(l/2!=r/2) {
				if(l%2==0) ans[i.nd]+=tr[l+1];
				if(r%2==1) ans[i.nd]+=tr[r-1];
				l/=2; r/=2;
			}
		}
	}
	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:82:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  while(N<V[x].size()) N*=2;
      |        ~^~~~~~~~~~~~
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:107:2: note: in expansion of macro 'rep'
  107 |  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: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5