Submission #720970

#	Time	Username	Problem	Language	Result	Execution time	Memory
720970		qwerasdfzxcl	Meetings (JOI19_meetings)	C++17	29 / 100	3044 ms	15372 KiB

meetings

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

using namespace std;
typedef long long ll;
int mp[2020][2020], qcnt;

int query(int x, int y, int z){
	if (x==1){
		if (y > z) swap(y, z);
		if (mp[y][z]) return mp[y][z];
		assert(qcnt++ <= 100000);
		return mp[y][z] = Query(x-1, y-1, z-1) + 1;
	}
	return Query(x-1, y-1, z-1) + 1;
}

void answer(int x, int y){
	if (x > y) swap(x, y);
	Bridge(x-1, y-1);
}

void dfs(int s, const vector<int> &a){
	vector<vector<int>> subtree;
	for (const auto &x:a){
		bool flag = 0;
		for (auto &V:subtree){
			if (query(1, x, V[0])!=s){
				flag = 1;
				V.push_back(x);
				break;
			}
		}

		if (flag) continue;
		subtree.emplace_back();
		subtree.back().push_back(x);
	}

	for (auto &V:subtree){
		vector<int> C = V;
		while(C.size() > 1){
			int x = C.back(); C.pop_back();
			int y = C.back(); C.pop_back();
			int z = query(1, x, y);

			if (x==z) C.push_back(x);
			if (y==z) C.push_back(y);
		}

		answer(s, C[0]);
		V.erase(find(V.begin(), V.end(), C[0]));
		dfs(C[0], V);
	}
}

void Solve(int N) {
	vector<int> a;
	for (int i=2;i<=N;i++) a.push_back(i);
	dfs(1, a);
}

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