Submission #946834

#	Time	Username	Problem	Language	Result	Execution time	Memory
946834		shoryu386	Meetings (JOI19_meetings)	C++17	29 / 100	1633 ms	748 KiB

meetings

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

using namespace std;

void Solve(int N) {
	
	//force 0 to be the root
	//for every C, we try every B to determine parenthood
	
	vector<int> ancestors[N+7];
	
	for (int C = 1; C < N; C++){
		
		ancestors[C].push_back(0);
		for (int B = 1; B < N; B++){
			if (B == C) continue;
			
			if (Query(0, B, C) == B){
				ancestors[C].push_back(B);
			}
		}
		
	}
	
	/*
	for (int x = 0; x < N; x++){
		cout << "anc " << x << '\n';
		for (auto y : ancestors[x]) cout << y << ' ';
		cout << "\n\n";
	}
	* */
	
	
	int par[N+7];
	for (int C = 1; C < N; C++){
		int largestPar = -1;
		int largestParLoc = -1;
		
		for (auto anc : ancestors[C]){
			if ( ((int)(ancestors[anc].size())) >= largestPar){
				largestPar = ancestors[anc].size();
				largestParLoc = anc;
			}
		}
		
		par[C] = largestParLoc;
	}
	
	for (int x = 1; x < N; x++){
		
		//cerr << x << ' ' << par[x] << '\n';
		
		if (x < par[x]) Bridge(x, par[x]);
		else Bridge(par[x], x);
	}
}

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