제출 #1170976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170976		4QT0R	Meetings (JOI19_meetings)	C++20	0 / 100	986 ms	652 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

pair<int,int> correct(pair<int,int> p){
	if (p.first>p.second)swap(p.first,p.second);
	return p;
}

void Solve(int N){
	set<pair<int,int>> odc;
	vector<bool> leaf(N,true);
	vector<int> deg(N);
	int sr=Query(0,1,2);
	for (int i = 0; i<3; i++){
		if (sr!=i){
			odc.insert(correct({sr,i}));
			deg[sr]++;
			deg[i]++;
		}
	}
	leaf[sr]=false;
	for (int i = 3; i<N; i++){
		int kon1=-1,kon2=-1,lca=-1;
		for (auto [a,b] : odc){
			kon1=a;
			kon2=b;
			lca = Query(i,a,b);
			if (lca==i || (lca==a && leaf[a]) || (lca==b && leaf[b]))break;
			kon1=-1;
		}
		if (kon1==-1 || (lca==kon1 && leaf[kon1]) || (lca==kon2 && leaf[kon2])){
			odc.insert(correct({i,lca}));
			deg[i]++;
			deg[lca]++;
			if (leaf[lca])leaf[lca]=false;
		}
		else{
			odc.erase(correct({kon1,kon2}));
			odc.insert(correct({kon1,i}));
			odc.insert(correct({kon2,i}));
			leaf[i]=false;
		}
	}
	for (auto [a,b] : odc)Bridge(a,b);
}

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