Submission #726441

#	Time	Username	Problem	Language	Result	Execution time	Memory
726441		FatihSolak	Meetings (JOI19_meetings)	C++17	100 / 100	788 ms	1096 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define N 2005
using namespace std;
vector<int> adj[N];
bool ban[N];
bool vis[N];
bool added[N];
int sub[N];
void Solve(int n) {
	adj[0].push_back(1);
	adj[1].push_back(0);
	added[0] = added[1] = 1;
	function<void(int,int)> add = [&](int x,int nw){
		// cout << "HEY" << x << " " << nw << endl;
		for(int i = 0;i<n;i++){
			vis[i] = 0;
		}
		function<void(int)> dfs = [&](int v){
			vis[v] = 1;
			sub[v] = 1;
			for(auto u:adj[v]){
				if(vis[u] || ban[u])continue;
				dfs(u);
				sub[v] += sub[u];
			}
			// cout << v << ' ' << sub[v] << endl; 
		};
		dfs(x);
		int centroid = -1;
		for(int i = 0;i<n;i++){
			if(vis[i]){
				bool ok = 1;
				ok &= 2*(sub[x] - sub[i]) <= sub[x];
				for(auto u:adj[i]){
					if(vis[u] && sub[u] < sub[i])
						ok &= sub[u] * 2 <= sub[x];
				}
				if(ok)
					centroid = i;
			}
		}
		assert(centroid != -1);
		// cout << centroid << endl;
		for(int i = 0;i<n;i++){
			vis[i] = 0;
		}
		dfs(centroid);
		vector<int> tmp;
		for(auto u:adj[centroid]){
			if(vis[u])
				tmp.push_back(u);
		}
		sort(tmp.begin(),tmp.end(),[&](int a,int b){
			return sub[a] > sub[b];
		});
		for(int i = 0;i < tmp.size();i+=2){
			if(i + 1 != tmp.size()){
				int val = Query(nw,tmp[i],tmp[i+1]);
				if(val == tmp[i]){
					ban[centroid] = 1;
					add(tmp[i],nw);
					return;
				}
				if(val == tmp[i+1]){
					ban[centroid] = 1;
					add(tmp[i+1],nw);
					return;
				}
				int val2 = Query(nw,tmp[i],centroid);
				if(nw == val2){
					adj[nw].push_back(tmp[i]);
					adj[nw].push_back(centroid);
					adj[tmp[i]].push_back(nw);
					adj[centroid].push_back(nw);
					for(auto &u:adj[tmp[i]]){
						if(u == centroid){
							swap(u,adj[tmp[i]].back());
							adj[tmp[i]].pop_back();
							break;
						}
					}
					for(auto &u:adj[centroid]){
						if(u == tmp[i]){
							swap(u,adj[centroid].back());
							adj[centroid].pop_back();
							break;
						}
					}
					return;
				}
				else if(!added[val2]){
					added[val2] = 1;
					adj[val2].push_back(nw);
					adj[nw].push_back(val2);
					adj[val2].push_back(tmp[i]);
					adj[val2].push_back(centroid);
					adj[tmp[i]].push_back(val2);
					adj[centroid].push_back(val2);
					for(auto &u:adj[tmp[i]]){
						if(u == centroid){
							swap(u,adj[tmp[i]].back());
							adj[tmp[i]].pop_back();
							break;
						}
					}
					for(auto &u:adj[centroid]){
						if(u == tmp[i]){
							swap(u,adj[centroid].back());
							adj[centroid].pop_back();\
							break;
						}
					}
					return;
				}
				else{
					val2 = Query(nw,tmp[i + 1],centroid);
					if(nw == val2){
						adj[nw].push_back(tmp[i+1]);
						adj[nw].push_back(centroid);
						adj[tmp[i+1]].push_back(nw);
						adj[centroid].push_back(nw);
						for(auto &u:adj[tmp[i+1]]){
							if(u == centroid){
								swap(u,adj[tmp[i+1]].back());
								adj[tmp[i+1]].pop_back();
								break;
							}
						}
						for(auto &u:adj[centroid]){
							if(u == tmp[i+1]){
								swap(u,adj[centroid].back());
								adj[centroid].pop_back();
								break;
							}
						}
						return;
					}
					else if(!added[val2]){
						added[val2] = 1;
						adj[val2].push_back(nw);
						adj[nw].push_back(val2);
						adj[val2].push_back(tmp[i+1]);
						adj[val2].push_back(centroid);
						adj[tmp[i+1]].push_back(val2);
						adj[centroid].push_back(val2);
						for(auto &u:adj[tmp[i+1]]){
							if(u == centroid){
								swap(u,adj[tmp[i+1]].back());
								adj[tmp[i+1]].pop_back();
								break;
							}
						}
						for(auto &u:adj[centroid]){
							if(u == tmp[i+1]){
								swap(u,adj[centroid].back());
								adj[centroid].pop_back();
								break;
							}
						}
						return;
					}
				}
			}
			int val = Query(nw,tmp[i],centroid);
			if(val == tmp[i]){
				ban[centroid] = 1;
				add(tmp[i],nw);
				return;
			}
			int val2 = val;
			if(nw == val2){
				adj[nw].push_back(tmp[i]);
				adj[nw].push_back(centroid);
				adj[tmp[i]].push_back(nw);
				adj[centroid].push_back(nw);
				for(auto &u:adj[tmp[i]]){
					if(u == centroid){
						swap(u,adj[tmp[i]].back());
						adj[tmp[i]].pop_back();
						break;
					}
				}
				for(auto &u:adj[centroid]){
					if(u == tmp[i]){
						swap(u,adj[centroid].back());
						adj[centroid].pop_back();
						break;
					}
				}
				return;
			}
			else if(!added[val2]){
				added[val2] = 1;
				adj[val2].push_back(nw);
				adj[nw].push_back(val2);
				adj[val2].push_back(tmp[i]);
				adj[val2].push_back(centroid);
				adj[tmp[i]].push_back(val2);
				adj[centroid].push_back(val2);
				for(auto &u:adj[tmp[i]]){
					if(u == centroid){
						swap(u,adj[tmp[i]].back());
						adj[tmp[i]].pop_back();
						break;
					}
				}
				for(auto &u:adj[centroid]){
					if(u == tmp[i]){
						swap(u,adj[centroid].back());
						adj[centroid].pop_back();
						break;
					}
				}
				return;
			}
		}
		// cout << "HEYY" << endl;
		// cout << nw << ' ' << centroid << endl;
		adj[nw].push_back(centroid);
		adj[centroid].push_back(nw);
	};
	for(int i = 2;i<n;i++){
		if(added[i])continue;
		// for(int j = 0;j<n;j++){
		// 	for(auto u:adj[j]){
		// 		cout << "EDGE:";
		// 		cout << u << ' ' << j << endl;
		// 	}

		// }
		// cout << i << endl;
		add(0,i);
		added[i] = 1;
		for(int j = 0;j<n;j++){
			ban[j] = 0;
		}
	}
	for(int j = 0;j<n;j++){
		for(auto u:adj[j]){
			if(u < j){
				// cout << "EDGE:";
				// cout << u << ' ' << j << endl;
				Bridge(u,j);
			}
		}

	}
}

Compilation message (stderr)

meetings.cpp: In lambda function:
meetings.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i = 0;i < tmp.size();i+=2){
      |                 ~~^~~~~~~~~~~~
meetings.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    if(i + 1 != tmp.size()){
      |       ~~~~~~^~~~~~~~~~~~~

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