제출 #726723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726723		josanneo22	Meetings (JOI19_meetings)	C++17	100 / 100	629 ms	5224 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 2e3 + 5;
using ii = pair<int, int>;
 
int n;
set<ii> ans;
unordered_map<int, unordered_map<int, unordered_map<int, int>>> mem;
int ask(int u, int v, int w) {
	{
		int mn = min({u, v, w});
		int mx = max({u, v, w});
		int md = u + v + w - mn - mx;
		u = mn, v = md, w = mx;
	}
	if(u == v or v == w) return v;
	if(mem[u][v].find(w) == mem[u][v].end()) return mem[u][v][w] = Query(u, v, w);
	else return mem[u][v][w];
}
 
void add_edge(int u, int v) {
	if(u > v) swap(u, v);
	ans.insert(ii(u, v));
}
 
void solve(vector<int> &s) {
	if(s.size() < 2) return;
	if(s.size() == 2) {
		add_edge(s[0], s[1]);
		return;
	}
	shuffle(s.begin(), s.end(), rng);
	set<int> path_nodes;
	unordered_map<int, int> mp;
	int p = s[0], q = s[1];
	for(int u : s) {
		mp[u] = ask(p, q, u);
		path_nodes.insert(mp[u]);
	}
	path_nodes.erase(p);
	path_nodes.erase(q);
	vector<int> path(path_nodes.begin(), path_nodes.end());
	shuffle(path.begin(), path.end(), rng);
	sort(path.begin(), path.end(), [&](int u, int v){ return ask(p, u, v) == u; });
	for(int i = 1; i < path.size(); i++) {
		add_edge(path[i - 1], path[i]);
	}
	if(path.size()) {
		add_edge(path[0], p);
		add_edge(path.back(), q);
	} else add_edge(p, q);
	unordered_map<int, vector<int>> to;
	for(auto i : mp) {
		to[i.second].emplace_back(i.first);
	}
	for(auto i : to) {
		solve(i.second);
	}
}
 
void Solve(int N) {
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);
	solve(v);
	for(ii i : ans) Bridge(i.first, i.second);
}

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'void solve(std::vector<int>&)':
meetings.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 1; i < path.size(); i++) {
      |                 ~~^~~~~~~~~~~~~

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