Submission #508872

#	Time	Username	Problem	Language	Result	Execution time	Memory
508872		couplefire	Meetings (JOI19_meetings)	C++17	100 / 100	862 ms	1064 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
 
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
vector<vector<int>> stuff;
 
void calc(vector<int> v){
    if((int)v.size()==1) return;
    int n = v.size();
    shuffle(v.begin(), v.end(), rng);
    int a = v[0], b = v[1];
    vector<int> path = {a, b};
    for(int i = 2; i<n; ++i)
        if(Query(a, b, v[i])==v[i])
            path.push_back(v[i]);
    sort(path.begin(), path.end(), [&](int x, int y){
        if(a==x) return true;
        if(a==y) return false;
        return Query(a, x, y)==x;
    });
    for(int i = 0; i<(int)path.size()-1; ++i)
        Bridge(min(path[i], path[i+1]), max(path[i], path[i+1]));
    for(auto x : path)
        stuff[x].clear();
    stuff[a] = {a}; stuff[b] = {b};
    for(int i = 2; i<n; ++i)
        stuff[Query(a, b, v[i])].push_back(v[i]);
    for(auto x : path)
        calc(stuff[x]);
}
 
void Solve(int n){
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    stuff.resize(n); calc(v);
}

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