Submission #790277

#	Time	Username	Problem	Language	Result	Execution time	Memory
790277		fabijan_cikac	Inside information (BOI21_servers)	C++17	5 / 100	112 ms	30712 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 = 120100;
const int MAXQ = 2 * N;
const int INF = 2 * N;
 
int n, k, sol[MAXQ];
vector<edge> v[N]; vector<Q> l;
 
int cnt[MAXQ], fen[MAXQ];
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){
	//cout << x << endl;
	++x;
	for (int i = x; i <= MAXQ; 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], sub_idx[N], leave[N], reach[N];
int joined[N], reached[N];
void dfs2(int x, int flag, int flag2){
	bio[x] = 1; sub_idx[x] = flag;
	for (edge e: v[x]){
		if (!bio[e.y]){
			if (joined[x] && join[x] > e.w){
				join[e.y] = join[x];
				joined[e.y] = 1;
			}
			
			if (reached[x] && reach[x] < e.w){
				reach[e.y] = e.w;
				reached[e.y] = 1;
			}
			leave[e.y] = flag2;
			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 x, vector<int> qQ, vector<int> qC){
	/*cout << x << ":" << endl;
	for (int y: qQ)
		cout <<y << ' ';
	cout << endl;
	for (int y: qC)
		cout <<y << ' ';
	cout << endl;*/
	//find centroid
	nodes.clear(); dfs(x);
	int node = findCentroid(x); bio[node] = 1;
	/*for (int i = 0; i < n; ++i)
		cout << bio[i];
	cout << endl;*/
	
	//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; leave[e.y] = e.w;
			joined[e.y] = 1; reached[e.y] = 1;
			reach[e.y] = e.w; dfs2(e.y, i, e.w);
		}
	}
	/*for (int y: nodes)
		cout << y << " -> "<< "j: " << join[y] << ' ' << "l: " << leave[y] << ' ' << "r: " << reach[y] << endl;
	*/
	//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]){
			//cout << "Q? " << l[idx].x << ' ' << l[idx].y << endl;
			if (joined[y] && reached[x] && leave[x] > join[y] && reach[x] < idx)
				sol[idx] = 1;
			//cout << "!!!!!!!!!!! " << sol[idx] << endl;
		}
		else{
			//cout << "wtf " << sub_idx[l[idx].x] << endl;
			nqQ[sub_idx[x]].pb(idx);
		}
	}
	
	//solve/push query of type C
	//cout << "ok" << endl;
	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());
	
	for (ppp p: sweep){
		if (p.S.F == 0){
			//cout << " + " << p.F << ' '<< p.S.S << endl;
			++cnt[p.S.S]; upd(p.S.S, 1);
		}
		else{
			int x = l[p.F].x;
			if (x == node)
				sol[p.F] += (sum(MAXQ - 1) + 1);
			else{
				if (!joined[x])
					continue;
				int res = sol[p.F];
				sol[p.F] += (sum(MAXQ - 1) - sum(join[x]));
				if (joined[x] && join[x] <= p.F) ++sol[p.F];
				//cout << "% " << ' ' << x << ' ' << p.S.F << ' '<< p.F << ' ' << sol[p.F] - res << endl;
			}
		}
		
	}
	for (int y: nodes){
		if (cnt[leave[y]] != 0){
			upd(leave[y], -cnt[leave[y]]); cnt[leave[y]] = 0;
		}
	}
	for (int idx: qC){
		//cout << "ov: " << l[idx].x << ' ' << sub_idx[l[idx].x] << " -> " << idx << endl;
		nqC[sub_idx[l[idx].x]].pb(idx);
	}
	//cout << "&)%&&%%) "<< nqC[1].size() << endl;
	
	//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];
		/*cout << "&&&&&&&&& " << e.y << endl;
		for (int y: nqC[i]) cout << y << ' ';
		cout << endl;*/
		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:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   if (subtree[e.y] > (nodes.size() / 2)){
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'void solve(int, std::vector<int>, std::vector<int>)':
servers.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for (int i = 0; i < v[node].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~
servers.cpp:174:9: warning: unused variable 'res' [-Wunused-variable]
  174 |     int res = sol[p.F];
      |         ^~~
servers.cpp:197:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |  for (int i = 0; i < v[node].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 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