Submission #131489

#	Time	Username	Problem	Language	Result	Execution time	Memory
131489		hamzqq9	Meetings (JOI19_meetings)	C++14	100 / 100	1925 ms	1272 KiB

meetings

#include "meetings.h"	
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define N 300005
using namespace std;

int gsb;
vector<int> u;
vector<multiset<int>> v;
vector<int> sub;
vector<int> f;

struct change {

	int a,b,mean;

};

int fcnt(int node,int ata) {

	for(auto x:v[node]) {

		if(x==ata || f[x]) continue ;

		if(sub[x]>gsb/2) return fcnt(x,node);

	}

	return node;

}

void fsubs(int node,int ata) {

	sub[node]=1;

	for(auto x:v[node]) {

		if(x==ata || f[x]) continue ;

		fsubs(x,node);

		sub[node]+=sub[x];

	}

}

void solve(int node,int nw) {

	fsubs(node,0);

	gsb=sub[node];

	int cnt=fcnt(node,0);

	vector<change> q;

	f[cnt]=1;

	for(auto x:v[cnt]) {

		if(f[x]) continue ;

		int mid=Query(nw,cnt,x);

		if(mid==cnt) continue ;

		if(mid==x) {

			solve(x,nw);

			return ;

		}

		if(mid==nw) {

			q.pb({cnt,nw,1});
			q.pb({nw,x,1});
			q.pb({cnt,x,-1});

			break ;

		}

		q.pb({cnt,mid,1});
		q.pb({mid,x,1});
		q.pb({nw,mid,1});
		q.pb({cnt,x,-1});

		break ;

	}

	if(!sz(q)) q.pb({cnt,nw,1});

	for(auto x:q) {

		if(x.mean==1) {

			v[x.a].insert(x.b);
			v[x.b].insert(x.a);

		}
		else {

			v[x.a].erase(v[x.a].find(x.b));
			v[x.b].erase(v[x.b].find(x.a));

		}

		u[x.a]=u[x.b]=1;

	}

}

void Solve(int n) {

	u=sub=vector<int>(n,0);
	v=vector<multiset<int>>(n);

	mt19937 rnd(time(NULL));

	vector<int> order;

	for(int i=0;i<n;i++) {

		order.pb(i);

	}

	shuffle(all(order),rnd);

	int cnt=0;
	int root;

	for(int i=0;i<n;i++,++cnt) {

		if(u[order[i]]) continue ;

		if(!cnt) u[root=order[i]]=1;
		else if(cnt==1) {

			v[root].insert(order[i]);
			v[order[i]].insert(root);

			u[order[i]]=1;

		}
		else {

			f=vector<int>(n,0);

			solve(root,order[i]);

		}

	}

	for(int i=0;i<n;i++) {

		for(auto x:v[i]) {

			if(x>i) Bridge(i,x); 
	
		}

	}
 
}

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