Submission #1172457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172457		danglayloi1	Meetings (JOI19_meetings)	C++20	100 / 100	1175 ms	988 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int get(int l, int r)
{
    return l+mt()*mt()%(r-l+1);
}
// void Bridge(int u, int v)
// {
//     cout<<"haha"<<u<<' '<<v<<'\n';
// }
// int Query(int u, int v, int w)
// {
//     cout<<u<<' '<<v<<' '<<w<<'\n';
//     int x;
//     cin>>x;
//     return x;
// }
int st, en;
bool cmp(int a, int b)
{
    if(a==st) return 1;
    if(a==en) return 0;
    if(b==st) return 0;
    if(b==en) return 1;
    return Query(st, a, b)==a;
}
void dfs(int u, vector<int> ver)
{
    if(ver.size()==1) return;
    if(ver.size()==2)
    {
        if(ver[0]>ver[1]) swap(ver[0], ver[1]);
        Bridge(ver[0], ver[1]);
        return;
    }
    shuffle(ver.begin(), ver.end(), mt);
    map<int, vector<int>> mp;
    mp.clear();
    int v=u;
    while(v==u)
    {
        int pos=get(0, ver.size()-1);
        v=ver[pos];
    }
    mp[u].emplace_back(u);
    mp[v].emplace_back(v);
    for(int x:ver)
    {
        if(x==u || x==v) continue;
        int nw=Query(u, v, x);
        mp[nw].emplace_back(x);
    }
    vector<int> path;
    path.clear();
    for(auto it:mp)
    {
        path.emplace_back(it.fi);
        dfs(it.fi, it.se);
    }
    st=u, en=v;
    sort(path.begin(), path.end(), cmp);
    for(int i = 1; i < path.size(); i++)
        Bridge(min(path[i-1], path[i]), max(path[i-1], path[i]));
}
void Solve(int n)
{
    vector<int> tmp;
    tmp.clear();
    for(int i = 0; i < n; i++)
        tmp.emplace_back(i);
    shuffle(tmp.begin(), tmp.end(), mt);
    dfs(tmp[0], tmp);
}
// int main()
// {
//     Solve(5);
// }

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