Submission #946927

#	Time	Username	Problem	Language	Result	Execution time	Memory
946927		penguin133	Meetings (JOI19_meetings)	C++17	0 / 100	1729 ms	748 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#include "meetings.h"
 
 
int par[2005];
int getr(int x){return par[x] == x ? x : par[x] = getr(par[x]);}
void merge(int a, int b){
	a = getr(a); b =getr(b);
	par[b] = a;
}
 
set <int> adj[2005];
int mx, ind, cc, cur;
 
void dfs(int x, int par, int d){
	if(par != -1){
		if(Query(x, par, cur) == cur){
			cc = 1;
			adj[x].erase(par);
			adj[par].erase(x);
			adj[x].insert(cur);
			adj[cur].insert(x);
			adj[cur].insert(par);
			adj[par].insert(cur);
			return;
		}
	}
	if(cc)return;
	if(d > mx && x && Query(0, x, cur) == x){
		mx = d, ind = x;
	}
	for(auto i : adj[x]){
		if(i != par){
			dfs(i, x, d + 1);
			if(cc)return;
		}
	}
}
 
void Solve(int N) {
  for(int i = 0; i < N; i++)adj[i].clear();
  for(int i = 1; i < N; i++){
	  cc = mx = ind = 0;
	  cur = i;
	  dfs(0, -1, 1);
	  if(!cc){
		  adj[ind].insert(i);
		  adj[i].insert(ind);
	  }
  }
  for(int i = 0; i < N; i++){
	  for(auto j : adj[i])if(j > i)Bridge(i, j);
  }
}

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