Submission #790441

#	Time	Username	Problem	Language	Result	Execution time	Memory
790441		fabijan_cikac	Inside information (BOI21_servers)	C++17	100 / 100	387 ms	51184 KiB

servers

#include <bits/stdc++.h>
 
using namespace std;
 
#define pp pair<int, int>
#define ppp pair<int, pp>
#define F first
#define S second
#define pb push_back
 
struct Q{
	char ch; int x, y;
};
 
struct edge{
	int y, w;
};
 
const int N = 2 * 120100;
 
int n, k, sol[N];
vector<edge> v[N]; vector<Q> l;
 
int cnt[N], fen[N];
int sum(int x){
	++x; int res = 0;
	for (int i = x; i > 0; i -= i & (-i))
		res += fen[i];
	return res;
}
 
void upd(int x, int val){
	++x;
	for (int i = x; i < N; i += i & (-i))
		fen[i] += val;
}
 
int bio[N], subtree[N], par[N];
vector<int> nodes;
int dfs(int x){
	nodes.pb(x);
	bio[x] = 1; int res = 1;
	for (edge e: v[x]){
		if (!bio[e.y]){
			par[e.y] = x;
			res += dfs(e.y);
		}
	}
	subtree[x] = res; bio[x] = 0;
	return subtree[x];
}
 
int join[N], first[N], sub_idx[N], leave[N], reach[N];
int joined[N], reached[N];
void dfs2(int x, int flag, int flag2){
	bio[x] = 1; leave[x] = flag2; sub_idx[x] = flag;
	for (edge e: v[x]){
		if (!bio[e.y]){
			if (joined[x] && first[x] > e.w){
				join[e.y] = join[x];
				joined[e.y] = 1; first[e.y] = e.w;
			}
			
			if (reached[x] && reach[x] < e.w){
				reach[e.y] = e.w;
				reached[e.y] = 1;
			}
			dfs2(e.y, flag, flag2);
		}
	}
	bio[x] = 0;
}
 
int findCentroid(int x){
	bio[x] = 1;
	for (edge e: v[x]){
		if (bio[e.y]) continue;
		if (subtree[e.y] > (nodes.size() / 2)){
			int res = findCentroid(e.y);
			bio[x] = 0; return res;
		}
	}
	return x;
}
 
void solve(int root, vector<int> qQ, vector<int> qC){
	//find centroid
	nodes.clear(); dfs(root);
	int node = findCentroid(root); bio[node] = 1;
	
	//calc. join, reach & leave time for nodes
	join[node] = 0, reach[node] = 0, leave[node] = 0;
	joined[node] = 1; reached[node] = 1;
	sub_idx[node] = v[node].size();
	for (int i = 0; i < v[node].size(); ++i){
		edge e = v[node][i];
		if (!bio[e.y]){
			join[e.y] = e.w; first[e.y] = e.w;
			joined[e.y] = 1; reached[e.y] = 1;
			reach[e.y] = e.w; dfs2(e.y, i, e.w);
		}
	}
	
	//clear already used storage for pushed queryes (Q/C)
	vector<vector<int> > nqQ, nqC;
	nqQ.resize(v[node].size() + 1); nqC.resize(v[node].size() + 1);
		
	//solve/push query of type Q
	for (int idx: qQ){
		int x = l[idx].x, y = l[idx].y;
		if (x == node || y == node){
			if (x == node && y == node)
				sol[idx] = 1;
			else if (x == node){
				if (joined[y] && join[y] < idx)
					sol[idx] = 1;
			}
			else if (y == node){
				if (reached[x] && reach[x] < idx)
					sol[idx] = 1;
			}
		}
		else if (sub_idx[x] != sub_idx[y]){
			if (joined[y] && reached[x] && leave[x] > join[y] && reach[x] < idx)
				sol[idx] = 1;
		}
		else nqQ[sub_idx[x]].pb(idx);
	}
	
	//solve/push query of type C
	vector<ppp> sweep;
	for (int idx: qC)
		sweep.pb({idx, {1, -1}});
	for (int y: nodes){
		if (reached[y] && y != node)
			sweep.pb({reach[y], {0, leave[y]}});
	}
	sort(sweep.begin(), sweep.end());
	
	int all_sum = 0;
	for (ppp p: sweep){
		if (p.S.F == 0){
			++cnt[p.S.S]; upd(p.S.S, 1);
			++all_sum;
		}
		else{
			int x = l[p.F].x;
			if (x == node)
				sol[p.F] += (all_sum + 1);
			else{
				if (!joined[x]) continue;
				sol[p.F] += (all_sum - sum(join[x]));
				if (join[x] <= p.F) ++sol[p.F];
			}
		}
	}
	for (edge e: v[node]){
		if (cnt[e.w] != 0){
			upd(e.w, -cnt[e.w]); cnt[e.w] = 0;
		}
	}
	
	for (int idx: qC) nqC[sub_idx[l[idx].x]].pb(idx);
	
	//further decompose
	for (int y: nodes){
		joined[y] = 0; reached[y] = 0;
	}
	for (int i = 0; i < v[node].size(); ++i){
		edge e = v[node][i];
		if (!bio[e.y]) solve(e.y, nqQ[i], nqC[i]);
	}
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> k; vector<int> qQ, qC;
	l.pb({'C', 0});
	for (int i = 1; i <= n + k - 1; ++i){
		char ch; cin >> ch;
		if (ch == 'S'){
			int x, y; cin >> x >> y;
			--x, --y; v[x].pb({y, i}), v[y].pb({x, i});
			l.pb({ch, x, y});
		}
		else if (ch == 'Q'){
			int x, y; cin >> x >> y;
			l.pb({ch, x - 1, y - 1}); qQ.pb(i);
		}
		else{
			int x; cin >> x; qC.pb(i);
			l.pb({ch, x - 1, -1});
		}
	}
	
	solve(0, qQ, qC);
	for (int i = 1; i <= n + k - 1; ++i){
		if (l[i].ch == 'Q'){
			if (sol[i])
				cout << "yes";
			else cout << "no";
			cout << '\n';
		}
		else if (l[i].ch == 'C')
			cout << sol[i] << '\n';
	}
	
	return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int findCentroid(int)':
servers.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   if (subtree[e.y] > (nodes.size() / 2)){
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'void solve(int, std::vector<int>, std::vector<int>)':
servers.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (int i = 0; i < v[node].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~
servers.cpp:169:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |  for (int i = 0; i < v[node].size(); ++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