Submission #945038

#	Time	Username	Problem	Language	Result	Execution time	Memory
945038		pcc	Meetings (JOI19_meetings)	C++17	0 / 100	3 ms	1112 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

/*
  int x = Query(0, 1, 2);
    Bridge(u, u + 1);
*/

const int mxn = 2020;
set<int> tree[mxn];
int sz[mxn];
vector<int> perm;
bitset<mxn> done;
bitset<mxn> del;
int N;

void add_edge(int a,int b){
	tree[a].insert(b);
	tree[b].insert(a);
	cerr<<"ADD:"<<a<<' '<<b<<endl;
}

void del_edge(int a,int b){
	cerr<<"DEL:"<<a<<' '<<b<<endl;
	tree[a].erase(b);
	tree[b].erase(a);
}

void szdfs(int now,int par){
	sz[now] = 1;
	for(auto nx:tree[now]){
		if(del[nx]||nx==par)continue;
		szdfs(nx,now);
		sz[now] += sz[nx];
	}
	return;
}

int get_centroid(int now,int par,int tar){
	for(auto nxt:tree[now]){
		if(nxt == par||del[nxt])continue;
		if(sz[nxt]>tar)return get_centroid(nxt,now,tar);
	}
	return now;
}

void calc(int now,int tar){
	szdfs(now,now);
	cerr<<"CALC:"<<now<<' '<<tar<<' '<<sz[now]<<endl;
	if(sz[now] == 1){
		add_edge(now,tar);
		return;
	}
	else if(sz[now] == 2){
		int nx;
		for(auto &i:tree[now])if(!del[i])nx = i;
		int r = Query(now,nx,tar);
		if(r == tar){
			del_edge(now,nx);
			add_edge(tar,now);
			add_edge(tar,nx);
		}
		else{
			add_edge(r,tar);
		}
		return;
	}
	now = get_centroid(now,now,(sz[now]-1)/2);
	vector<int> ch;
	for(auto nxt:tree[now]){
		if(del[nxt])continue;
		ch.push_back(nxt);
	}
	del[now] = true;
	for(int i = 1;i<ch.size();i+=2){
		int a = ch[i-1],b = ch[i];
		int r = Query(a,b,tar);
		if(r == a){
			calc(a,tar);
			return;
		}
		else if(r == b){
			calc(b,tar);
			return;
		}
		else if(r == tar){
			r = Query(now,a,tar);
			if(r==tar)r = a;
			else if(r == now)r = b;
			else assert(false);
			del_edge(now,r);
			add_edge(tar,now);
			add_edge(tar,r);
			return;
		}
		else if(r != now){
			int tmp = Query(a,r,now);
			if(tmp == now){
				tmp = b;
			}
			else if(tmp == r){
				tmp = a;
			}
			else assert(false);
			del_edge(now,tmp);
			add_edge(now,r);
			add_edge(r,tmp);
			add_edge(r,tar);
			done[r] = true;
			return;
		}
	}
	if(ch.size()&1){
		int r = Query(now,ch.back(),tar);
		if(r == ch.back()){
			calc(ch.back(),tar);
			return;
		}
		else if(r == tar){
			del_edge(now,ch.back());
			add_edge(tar,now);
			add_edge(tar,ch.back());
			return;
		}
		else if(r != now){
			del_edge(ch.back(),now);
			add_edge(r,ch.back());
			add_edge(r,now);
			add_edge(r,tar);
			return;
		}
	}
	add_edge(now,tar);
	return;
}

void addpt(int tar){
	del.reset();
	calc(0,tar);
	done[tar] = true;
}
void answer(){
	for(int i = 0;i<N;i++){
		for(auto nx:tree[i]){
			if(nx>i)Bridge(i,nx);
		}
	}
	return;
}
void print(){
	for(int i = 0;i<N;i++){
		for(auto nx:tree[i]){
			cout<<i<<":"<<nx<<endl;
		}
	}
	return;
}

void Solve(int NN) {
	N = NN;
	srand(time(NULL));
	for(int i = 0;i<N;i++)perm.push_back(i);
	//random_shuffle(perm.begin(),perm.end());
	done[0] = true;
	for(auto &i:perm)if(!done[i])addpt(i);
	answer();
	cerr<<"HI"<<endl;
	return;
}

Compilation message (stderr)

meetings.cpp: In function 'void calc(int, int)':
meetings.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 1;i<ch.size();i+=2){
      |                ~^~~~~~~~~~
meetings.cpp:58:16: warning: 'nx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |   int r = Query(now,nx,tar);
      |           ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71