Submission #538730

#	Time	Username	Problem	Language	Result	Execution time	Memory
538730		dsyz	Experimental Charges (NOI19_charges)	C++17	100 / 100	73 ms	16724 KiB

charges

#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (100005)
int N,Q;
vector<pair<int,int> > v[MAXN];
int parent[20][MAXN];
int depth[MAXN];
int dist[MAXN];
int visited[MAXN];
void distdfs(ll x){
	visited[x] = 1;
	for(auto u : v[x]){
		if(visited[u.first] == 0){
			dist[u.first] = dist[x] + u.second;
			visited[u.first] = 1;
			distdfs(u.first);
		}
	}
}
void dfs(ll x,ll nodeparent,ll nodedepth){
	parent[0][x] = nodeparent;
	depth[x] = nodedepth;
	for(ll i = 0;i < v[x].size();i++){
		if(v[x][i].first != nodeparent){
			dfs(v[x][i].first,x,nodedepth + 1);
		}
	}
}
void lcainit(){
	for(ll i = 1;i < 20;i++){
		for(ll j = 0;j < N;j++){
			parent[i][j] = parent[i - 1][parent[i - 1][j]];
		}
	}
}
int lca(ll u,ll v){
	if(depth[u] > depth[v]){
		swap(u,v);
	}
	ll diff = depth[v] - depth[u];
	for(ll i = 0;i < 20;i++){
		if(diff & (1<<i)){
			v = parent[i][v];
		} 
	}
	if(u == v){
		return u;
	} 
	for(ll i = 19;i >= 0;i--){
		if(parent[i][u] != parent[i][v]){
			u = parent[i][u];
			v = parent[i][v];
		}
	}
	return parent[0][u];
}
int PAR1[MAXN];
int find_setPAR1(ll a){
	if(PAR1[a] == a) return a;
	PAR1[a] = find_setPAR1(PAR1[a]);
	return PAR1[a];
}
bool same_setPAR1(ll a,ll b){
	return find_setPAR1(a) == find_setPAR1(b);
}
void merge_setPAR1(ll a,ll b){
	PAR1[find_setPAR1(a)] = find_setPAR1(b);
}
int par[MAXN];
int find_set(ll a){
	if(par[a] == a) return a;
	par[a] = find_set(par[a]);
	return par[a];
}
bool same_set(ll a,ll b){
	return find_set(a) == find_set(b);
}
void merge_set(ll a,ll b){
	par[find_set(a)] = find_set(b);
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>Q;
	vector<pair<char,pair<ll,ll> > > queries;
	for(ll i = 0;i < N;i++){
		PAR1[i] = i;
	}
	for(ll i = 0;i < N;i++){
		par[i] = i;
	}
	vector<ll> components[N];
	for(ll i = 0;i < Q;i++){
		char c;
		cin>>c;
		ll a,b;
		cin>>a>>b;
		a--;
		b--;
		if(c == 'A'){
			v[a].push_back(make_pair(b,1));
			v[b].push_back(make_pair(a,1));
			queries.push_back(make_pair(c,make_pair(a,b)));
			merge_setPAR1(a,b);
		}else if(c == 'R'){
			v[a].push_back(make_pair(b,0));
			v[b].push_back(make_pair(a,0));
			queries.push_back(make_pair(c,make_pair(a,b)));
			merge_setPAR1(a,b);
		}else if(c == 'Q'){
			queries.push_back(make_pair(c,make_pair(a,b)));
		}		
	}
	for(ll i = 0;i < N;i++){
		components[find_setPAR1(i)].push_back(i);
	}
	ll a = -1;
	for(ll i = 0;i < N;i++){
		if(components[i].size() == 0) continue;
		if(a == -1){
			a = components[i][0];
		}else{
			ll b = components[i][0];
			v[a].push_back(make_pair(b,0));
			v[b].push_back(make_pair(a,0));
		}
	}
	dist[0] = 0;
	visited[0] = 1;
	distdfs(0);
	//dfs(0,0,0);
	//lcainit();
	for(ll i = 0;i < Q;i++){
		char c = queries[i].first;
		ll a,b;
		a = queries[i].second.first;
		b = queries[i].second.second;
		if(c == 'A'){
			merge_set(a,b);
		}else if(c == 'R'){
			merge_set(a,b);
		}else if(c == 'Q'){
			if(!same_set(a,b)){
				cout<<'?'<<'\n';
			}else{
				ll sum = dist[lca(a,b)];
				if(((dist[a] + dist[b]) - (2 * sum)) % 2 == 1){
					cout<<'A'<<'\n';
				}else{
					cout<<'R'<<'\n';
				}
			}
		}
	}
}

Compilation message (stderr)

charges.cpp: In function 'void dfs(ll, ll, ll)':
charges.cpp:24:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(ll i = 0;i < v[x].size();i++){
      |               ~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 12 / 12
• Subtask 5: 25 / 25
• Subtask 6: 31 / 31