Submission #799743

#	Time	Username	Problem	Language	Result	Execution time	Memory
799743		lovrot	Inside information (BOI21_servers)	C++17	100 / 100	430 ms	68856 KiB

servers

#include <cstdio> 
#include <cassert>
#include <algorithm> 
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef pair<int, int> pii;
typedef pair<int, pii> pip;
typedef pair<pii, pii> ppp;

const int N = 3e5 + 10; 
const int oo = 0x7FFFFFFF;

int n, m, ANS[N];
char Q[N];

vector<pii> G[N];
vector<int> QC[N];
vector<pip> QQ[N];

bool BAN[N], MON[N][2];
int FIR[N], LST[N];
int CMP[N], SIZ[N];

int F[N];
vector<int> IND;
vector<pip> S; 

void add(int x, int val) {
	for(x += 2; x < N; x += x & -x) F[x] += val;
}

int sum(int x) {
	int ret = 0;
	for(x += 2; x; x -= x & -x) ret += F[x];
	return ret;
}

void dfs(int u, int p) { // ako je 'u' root, 'p' mora bit jednak 'u'
	if(p == u) {
		FIR[u] = oo; 
		LST[u] = -oo;
		CMP[u] = u;
		MON[u][0] = MON[u][1] = 1;
	}
	SIZ[u] = 1;
	
	if(MON[u][0]) // trebas RUCNO querijat 
		for(int x : QC[u]) {
			if(p == u) {
				IND.PB(x);
				S.PB({0, {0, x}});
				++ANS[x];
			} else {
				IND.PB(x); 
				S.PB({FIR[u], {0, x}}); 			
				if(x > FIR[u]) ++ANS[x]; // update od centroida
			}
		}
	if(MON[u][1] && p != u) // trebas RUCNO dodat taj update 
		S.PB({FIR[u], {1, LST[u]}}); 

	for(pii e : G[u]) {
		int v = e.X, w = e.Y; 
		if(v == p || BAN[v]) continue;
		if(p == u) {
			FIR[v] = LST[v] = w;
			CMP[v] = v;
			MON[v][0] = MON[v][1] = 1;
		} else {
			FIR[v] = FIR[u];
			LST[v] = w;
			CMP[v] = CMP[u];
			MON[v][0] = MON[u][0] && LST[u] > w;
			MON[v][1] = MON[u][1] && LST[u] < w;
		}
		dfs(v, u); 
		SIZ[u] += SIZ[v];
	}
}

void centroid(int u, int p, int &cent, int siz) {
	SIZ[u] = 1;
	bool flag = true;
	for(pii e : G[u]) {
		int v = e.X, w = e.Y;
		if(v == p || BAN[v]) continue;
		centroid(v, u, cent, siz);
		SIZ[u] += SIZ[v];
		flag &= SIZ[v] <= siz / 2;
	}
	if(flag && siz - SIZ[u] <= siz / 2) cent = u;
}

void solve(int c, int siz) {
	IND.clear(); 
	S.clear(); 

	int old = c;
	centroid(c, c, c, siz); // 'c' postaje centroid
		
	swap(QQ[c], QQ[old]); 

	dfs(c, c); 
	
	sort(IND.begin(), IND.end());
	sort(S.begin(), S.end(), [](pip a, pip b) {
		return a.X > b.X || (a.X == b.X && a.Y < b.Y);
	});

	for(int i = 0; i < (int) IND.size() + 10; ++i) F[i] = 0;
	
	for(pip q : S) {
		int ind = q.Y.Y;
		int pos = q.Y.X == 0 ?  
			lower_bound(IND.begin(), IND.end(), ind) - IND.begin() :
			lower_bound(IND.begin(), IND.end(), ind) - IND.begin();
		if(q.Y.X == 0) 	ANS[ind] += sum(pos);
		else add(pos, 1);
	}
	for(pip q : QQ[c]) {
		int ind = q.X, u = q.Y.X, v = q.Y.Y;
		if(CMP[u] == CMP[v] && CMP[u] != c) QQ[CMP[u]].PB(q);
		else {
			if(v == c)
				ANS[ind] = MON[u][1] && LST[u] < ind;
			else 
				ANS[ind] = MON[u][1] && MON[v][0] && FIR[v] < FIR[u] && max(LST[u], FIR[v]) < ind; 
		}
	}

	BAN[c] = 1;
	for(pii e : G[c]) {
		int v = e.X; 
		if(BAN[v]) continue;
		solve(v, SIZ[v]);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i < n + m; ++i) {
		int u, v;
		scanf(" %c ", Q + i); 
		if(Q[i] == 'S') {
			scanf("%d%d", &u, &v); 
			G[u].PB({v, i}); 
			G[v].PB({u, i}); 
		} else if(Q[i] == 'Q') {
			scanf("%d%d", &u, &v); 
			QQ[1].PB({i, {u, v}});
		} else {
			scanf("%d", &u); 
			QC[u].PB(i); 
		}
	}

	solve(1, n); 
	for(int i = 1; i < n + m; ++i) {
		if(Q[i] == 'Q') printf("%s\n", ANS[i] ? "yes" : "no"); 
		else if(Q[i] == 'C') printf("%d\n", ANS[i]); 
	}
	return 0;
}

Compilation message (stderr)

servers.cpp: In function 'void centroid(int, int, int&, int)':
servers.cpp:91:16: warning: unused variable 'w' [-Wunused-variable]
   91 |   int v = e.X, w = e.Y;
      |                ^
servers.cpp: In function 'int main()':
servers.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
servers.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |   scanf(" %c ", Q + i);
      |   ~~~~~^~~~~~~~~~~~~~~
servers.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |    scanf("%d%d", &u, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~
servers.cpp:155:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |    scanf("%d%d", &u, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~
servers.cpp:158:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |    scanf("%d", &u);
      |    ~~~~~^~~~~~~~~~

• 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