Submission #979813

#	Time	Username	Problem	Language	Result	Execution time	Memory
979813		parlimoos	Meetings (JOI19_meetings)	C++14	100 / 100	489 ms	4944 KiB

meetings

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , sz;
set<int> g[2000];
int cs[2000];
bool blk[2000][2000] , ms[2000];
vector<arr(2)> blks;
int cnt = 0;

//int Query(int v , int u , int w){
//	cout << "Q : {" << v << " , " << u << " , " << w << "}\n";
//	int res;
//	cin >> res;
//	return res;
//}
//void Bridge(int v , int u){
//	cout << "There is an edge between " << v << " and " << u << ".\n";
//	string res;
//	cin >> res;
//	if(res == "no") exit(0);
//}
void dfs1(int v , int p){
	cs[v] = 1;
	for(int u : g[v]){
		if(blk[v][u] or u == p) continue;
		dfs1(u , v) , cs[v] += cs[u];
	}
}
int getCnt(int v , int p){
	for(int u : g[v]){
		if(blk[v][u] or u == p) continue;
		if(cs[u] > sz / 2) return getCnt(u , v);
	}
	return v;
}
void connect(int v , int u){
	g[v].insert(u) , g[u].insert(v);
}
void addIn(int v , int w , int u){
	g[v].erase(w) , g[w].erase(v);
	connect(v , u) , connect(w , u);
}
void setBlk(int v , int u , bool vl){
	blk[v][u] = vl , blk[u][v] = vl;
	if(vl) blks.pb({v , u});
}
void Solve(int N){
	n = N , cnt = 3;
	int x = Query(0 , 1 , 2);
	if(x >= 0 and x <= 2){
		int v = 0 , u = 1;
		if(3 - x == 2) u = 2;
		if(3 - x == 3) v = 2;
		connect(x , v) , connect(x , u);
	}else{
		ms[x] = 1 , cnt++;
		for(int v = 0 ; v < 3 ; v++) connect(x , v);
	}
	
	for(int v = 3 ; v < n ; v++){
		if(!g[v].empty()) continue;
		int r = 0;
		sz = cnt;
		while(sz > 1){
			dfs1(r , -1);
//			if(sz == 5){
//				for(int i = 0 ; i < n ; i++){
//					if(g[i].empty()) continue;
//					cout << i << " " << cs[i] << " : ";
//					for(int u : g[i]) cout << u << " , ";
//					cout << "||\n" << flush;
//				}
//			}
			int c = getCnt(r , -1);
//			cout << "Centroid is " << c << ".\n";
			vector<arr(2)> ord;
			for(int u : g[c]){
				if(blk[c][u]) continue;
				if(cs[u] > cs[c]) ord.pb({sz - cs[c] , u});
				else ord.pb({cs[u] , u});
			}
			sort(ord.bg() , ord.end() , [](arr(2) a , arr(2) b){
				return (a[0] > b[0]);
			});
			
			for(int i = 0 ; i < (int)ord.size() ; i += 2){
				if(i == (int)ord.size() - 1){
					int x = Query(ord[i][1] , c , v);
					if(x == ord[i][1]){
						sz = ord[i][0] , r = ord[i][1] , setBlk(c , ord[i][1] , 1);
						break;
					}else{
						sz = 0 , r = -1;
						if(x == c) r = c;
						else if(x == v) addIn(c , ord[i][1] , v);
						else{
							ms[x] = 1 , cnt++ , addIn(c , ord[i][1] , x) , connect(x , v);
						}
					}
				}else{
					auto u = ord[i] , w = ord[i + 1];
					int x = Query(v , u[1] , w[1]);
					sz = 0 , r = -1;
					if(x == u[1] or x == w[1]){
						sz = u[0] , r = x , setBlk(c , x , 1);
						if(x == w[1]) sz = w[0];
//						cout << w[0] << " " << w[1] << "$$\n";
						break;
					}else if(x == c){
						if(i < (int)ord.size() - 2) continue;
						r = c;
					}else if(x == v){
						if(Query(c , v , u[1]) == v) addIn(c , u[1] , v);
						else addIn(c , w[1] , v);
						break;
					}else{
						ms[x] = 1 , cnt++;
						if(Query(c , x , u[1]) == x){
							addIn(c , u[1] , x) , connect(x , v);
						}else{
							addIn(c , w[1] , x) , connect(x , v);
						}
						break;
					}
				}
			}
//			cout << "L\n" << flush;
		}
		if(r != -1) connect(r , v);
		for(auto b : blks) setBlk(b[0] , b[1] , 0);
		blks.cl() , cnt++;
//		cout << "_____\n" << flush;
	}
	
	for(int v = 0 ; v < n ; v++){
		for(int u : g[v]){
			if(u > v) continue;
			Bridge(u , v);
		}
	}
}

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