Submission #513810

#	Time	Username	Problem	Language	Result	Execution time	Memory
513810		fatemetmhr	Meetings (JOI19_meetings)	C++17	0 / 100	3070 ms	12384 KiB

meetings

//  ~Be name khoda~  //

#include "meetings.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

int n;
vector <int> adj[maxn5], tmp, av;
int mx[maxn5], sz[maxn5];
bool rem[maxn5];

inline void remo(int a, int b){
	tmp.clear();
	for(auto u : adj[a]) 
		if(u != b) tmp.pb(u);
	adj[a].clear();
	for(auto u : tmp)
		adj[a].pb(u);
	return;
}

inline void dfs(int v, int par){
	sz[v] = 1;
	mx[v] = 0;
	av.pb(v);
	for(auto u : adj[v]) if(u != par && !rem[u]){
		dfs(u, v);
		mx[v] = max(mx[v], sz[u]);
		sz[v] += sz[u];
	}
	return;
}


inline void add(int r, int v){
	av.clear();
	dfs(r, -1);
	int c = r;
	for(auto u : av)
		if(max(mx[u], int(av.size()) - sz[u]) < max(mx[c], int(av.size()) - sz[c]))
			c = u;
	int sub = -1;
	for(auto u : adj[c]) if(!rem[u]){
		int t = Query(c, u, v);
		if(t == v){
			remo(u, c);
			remo(c, u);
			adj[u].pb(v);
			adj[c].pb(v);
			adj[v].pb(u);
			adj[v].pb(c);
			return;
		}
		if(t == u){
			sub = u;
			break;
		}
	}
	if(sub != -1){
		rem[c] = true;
		add(sub, v);
		return;
	}
	adj[c].pb(v);
	adj[v].pb(c);
}

void Solve(int nn){
	n = nn;
	for(int i = 1; i < n; i++){
		fill(rem, rem + n + 5, false);
		add(0, i);
	}
	for(int i = 0; i < n; i++) for(auto u : adj[i])
		if(i < u) Bridge(i, u);
	return;
}

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