Submission #131567

#	Time	Username	Problem	Language	Result	Execution time	Memory
131567		ekrem	Meetings (JOI19_meetings)	C++14	100 / 100	1114 ms	1212 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define inf 1000000009
#define MAXN 2005

using namespace std;

typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;
typedef set < int > si;
#define siter set < int > :: iterator

int n, u[MAXN], say[MAXN];
set < int > s[MAXN], kal;
ii mx;

int sor(int x, int y, int z){
	if(x == y)return x;
	if(z == y)return z;
	if(x == z)return x;
	return Query(x - 1, y - 1, z - 1) + 1;
}

void hazirla(int node, int par){
	say[node] = 1;
	for(siter it = s[node].begin(); it != s[node].end(); it++)
		if(*it != par and !u[*it]){
			hazirla(*it, node);
			say[node] += say[*it];
		}
}



void dfs(int node, int par){
	// cout << par << " -> " << node << endl;
	if(par)
		Bridge(min(par, node) - 1, max(par, node) - 1);
	for(siter it = s[node].begin(); it != s[node].end(); it++)
		if(*it != par){
			dfs(*it, node);
		}
}

void ekle(int x, int y){
	s[x].insert(y);
	s[y].insert(x);
	// cout << x << " " << y << " geldi" << endl;
}


void centbul(int node, int x){
	hazirla(node, 0);
	int par = 0, t = say[node], f = 1;
	while(f){
		f = 0;
		mx = mp(0, 0);
		for(siter it = s[node].begin(); it != s[node].end(); it++)
			if(!u[*it] and *it != par)
				mx = max(mx, mp(say[*it], *it));
		if(mx.st > t/2){
			f = 1;
			par = node;
			node = mx.nd;
		}
	}
	// cout << x << " " << node << " " << mx.nd << " = ";
	if(!mx.nd){
		ekle(node, x);
		kal.erase(x);
		return;
	}
	int y = sor(x, node, mx.nd);
	// cout << y << endl;
	if(y == node){
		u[mx.nd] = 1;
		centbul(node, x);
		return;
	}
	if(y == mx.nd){
		u[node] = 1;
		centbul(mx.nd, x);
		return;
	}
	// cout << node << " " << mx.nd << "gitti " << endl;
	s[node].erase(mx.nd);
	s[mx.nd].erase(node);
	ekle(node, y);
	ekle(mx.nd, y);
	if(y != x)
		ekle(x, y);
	kal.erase(x);
	kal.erase(y);
}

void Solve(int nn) {n = nn;
	ekle(1, 2);
	for(int i = 3; i <= n; i++)
		kal.insert(i);
	while(!kal.empty()){
		int x = *kal.begin();

		memset(u, 0, sizeof u);
		centbul(1, x);
	}
	dfs(1, 0);
}

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