Submission #979776

#	Time	Username	Problem	Language	Result	Execution time	Memory
979776		parlimoos	Meetings (JOI19_meetings)	C++14	7 / 100	405 ms	262144 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 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 Solve(int N){
	n = N;
	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;
		g[x].insert(v) , g[x].insert(u) , g[v].insert(x) , g[u].insert(x);
	}else{
		ms[x] = 1;
		for(int v = 0 ; v < 3 ; v++) g[v].insert(x) , g[x].insert(v);
	}
	
	for(int v = 3 ; v < n ; v++){
		if(!g[v].empty()) continue;
		int r = 0;
		sz = n;
		while(sz > 1){
			dfs1(r , -1);
			int c = getCnt(r , -1);
			vector<arr(2)> ord;
			for(int u : g[c]){
				if(blk[c][u]) continue;
				if(cs[u] > cs[c]) ord.pb({cs[u] - 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];
						blk[c][ord[i][1]] = 1 , blk[ord[i][1]][c] = 1;
						blks.pb({c , ord[i][1]});
						break;
					}else if(x == c){
						sz = 0 , r = c;
					}else if(x == v){
						sz = 0 , r = -1 , g[c].erase(ord[i][1]) , g[ord[i][1]].erase(c);
						g[c].insert(v) , g[v].insert(c) , g[v].insert(ord[i][1]) , g[ord[i][1]].insert(v);
					}else{
						sz = 0 , r = -1 , g[c].erase(ord[i][1]) , g[ord[i][1]].erase(c);
						g[x].insert(v) , g[x].insert(ord[i][1]) , g[x].insert(c);
						g[v].insert(x) , g[ord[i][1]].insert(x) , g[c].insert(x);
						ms[x] = 1;
					}
				}else{
					auto u = ord[i] , w = ord[i + 1];
					int x = Query(v , u[1] , w[1]);
					if(x == u[1]){
						sz = u[0] , r = u[1];
						blk[c][u[1]] = 1 , blk[u[1]][c] = 1;
						blks.pb({c , u[1]});
						break;
					}else if(x == w[1]){
						sz = w[0] , r = w[1];
						blk[c][w[1]] = 1 , blk[w[1]][c] = 1;
						blks.pb({c , w[1]});
						break;
					}else if(x == c){
						if(i < (int)ord.size() - 2) continue;
						sz = 0 , r = c;
					}else if(x == v){
						sz = 0 , r = -1;
						int xx = Query(c , v , u[1]);
						if(xx == v){
							g[c].erase(u[1]) , g[u[1]].erase(c);
							g[v].insert(u[1]) , g[v].insert(c) , g[c].insert(v) , g[u[1]].insert(v);
						}else{
							g[c].erase(w[1]) , g[w[1]].erase(c);
							g[v].insert(w[1]) , g[v].insert(c) , g[c].insert(v) , g[w[1]].insert(v);
						}
					}else{
						int xx = Query(c , x , u[1]);
						sz = 0 , r = -1;
						if(xx == x){
							g[c].erase(u[1]) , g[u[1]].erase(c);
							g[x].insert(u[1]) , g[x].insert(v) , g[x].insert(c);
							g[u[1]].insert(x) , g[v].insert(x) , g[c].insert(x);
						}else{
							g[c].erase(w[1]) , g[w[1]].erase(c);
							g[x].insert(w[1]) , g[x].insert(v) , g[x].insert(c);
							g[w[1]].insert(x) , g[v].insert(x) , g[c].insert(x);
						}
						ms[x] = 1;
					}
				}
			}
		}
		if(r != -1) g[r].insert(v) , g[v].insert(r);
		for(auto b : blks){
			blk[b[0]][b[1]] = 0;
			blk[b[1]][b[0]] = 0;
		}
		blks.cl();
	}
	
	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: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71