Submission #1132917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132917		ByeWorld	Library (JOI18_library)	C++20	100 / 100	94 ms	540 KiB

library

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include "library.h"
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 1010;
const int SQRT = 610;
const int MAXA = 50;
const int MOD = 998244353;
const int INF = 1e9+10;
const int LOG = 21;
const ld EPS = 1e-12;

vector <int> que, adj[1010], ans;
vector <pii> edge;
int n;

struct dsu {
	int par[MAXN];
	vector <int> vec[MAXN];
	void bd(){
		for(int i=0; i<n; i++)
			par[i] = i, vec[i].pb(i);
	}
	int f(int x){
		return (par[x]==x ? x : par[x]=f(par[x]));
	}
	void mer(int x, int y){
		x = f(x); y = f(y);
		if(x==y) return;
		if(vec[x].size() > vec[y].size()) swap(x,y);
		par[x] = y;
		for(auto in : vec[x]) vec[y].pb(in);
	}
} DSU;
void dfs(int nw, int par){
	ans.pb(nw+1);
	for(auto nx : adj[nw]){
		if(nx==par) continue;
		dfs(nx, nw);
	}
}
void RESET(){
	for(int i=0;i<n;i++) que[i] = 0;
}
void RANGE(int x, int y){
	for(auto in : DSU.vec[DSU.f(x)]) que[in] = 1;
	for(auto in : DSU.vec[DSU.f(y)]) que[in] = 1;  
}
void Solve(int N)
{
	n = N;
	que.resize(n); DSU.bd();
	edge.pb({0,0});

	for(int i=1; i<n; i++){
		int l=0, r=edge.size()-1, mid=0, cnt=-1;
		while(l<=r){
			mid = md;
			RESET(); que[i] = 1;
			for(int j=0; j<=mid; j++) 
				RANGE(edge[j].fi, edge[j].se);
			if(Query(que) == mid+2) cnt = mid, l = mid+1;
			else r = mid-1;
		}
			// cout << i<<" i\n";
			// for(auto [x,y]:edge) cout << x << ' '<<y << "xy\n";
		if(cnt == edge.size()-1){
			edge.pb({i,i}); continue;
		}
		// cnt+1, merge 1 side
		RESET(); que[i] = 1; que[edge[cnt+1].fi] = 1;
		int le = -1, ri = -1;
		if(Query(que) == 1) le = edge[cnt+1].fi;
		else le = edge[cnt+1].se;

		if(edge.size()-1 < cnt+2){

			vector <pii> vec; 
			DSU.mer(i, le);
			adj[i].pb(le); adj[le].pb(i);
			// cout <<le << ' '<< i << "lei\n";
			for(auto [x,y] : edge){
				if(x==le) vec.pb({i, y});
				else if(y==le) vec.pb({i, x});
				else vec.pb({x,y});
			}
			swap(vec, edge);
			continue;

		}

		l = cnt+2, r=edge.size()-1, mid=0; int cnt2 = cnt+1;
		while(l<=r){
			mid = md;
			RESET(); que[i] = 1;
			for(int j=cnt+2; j<=mid; j++) 
				RANGE(edge[j].fi, edge[j].se);
			if(Query(que) == mid-cnt-1 + 1) cnt2 = mid, l = mid+1;
			else r = mid-1;
		}
		if(cnt2 < edge.size()-1){ // cnt2+1, merge ri
			RESET(); que[i] = 1; que[edge[cnt2+1].fi] = 1;
			if(Query(que) == 1) ri = edge[cnt2+1].fi;
			else ri = edge[cnt2+1].se;
		} else {
			vector <pii> vec; 
			DSU.mer(i, le);
			adj[i].pb(le); adj[le].pb(i);
			// cout <<le << ' '<< i << "lei\n";
			for(auto [x,y] : edge){
				if(x==le) vec.pb({i, y});
				else if(y==le) vec.pb({i, x});
				else vec.pb({x,y});
			}
			swap(vec, edge);
			continue;
		}

		DSU.mer(i, le); DSU.mer(ri, i);
		adj[i].pb(le); adj[le].pb(i);
		adj[i].pb(ri); adj[ri].pb(i);
		// cout << le << ' '<< i << ' '<< ri << " leri\n";

		vector <pii> vec; int pp = -1;
		for(auto [x,y] : edge){
			if(x==le || x==ri){
				if(pp==-1) pp = y;
				else vec.pb({pp, y});
			} else if(y==le || y==ri){
				if(pp==-1) pp = x;
				else vec.pb({pp, x});
			} else vec.pb({x,y});
		}
		swap(vec, edge);
	}
	int sta = 0;
	for(int i=0; i<n; i++) 
		if(adj[i].size() == 1) sta = i;
	dfs(sta, -1);

	assert(ans.size() == n);
	Answer(ans);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81