Submission #1171470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171470		danglayloi1	Meetings (JOI19_meetings)	C++20	29 / 100	1374 ms	1856 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;
const int nx=2e3+5;
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;
// }
void dfs(int p, vector<int> ver)
{
    if(ver.size()==2)
    {
        if(ver[0]>ver[1]) swap(ver[0], ver[1]);
        Bridge(ver[0], ver[1]);
        return;
    }
    int u;
    vector<int> cur;
    cur.clear();
    for(int i:ver) if(i!=p) cur.emplace_back(i);
    u=cur[get(0, cur.size()-1)];
    int mx=0;
    for(int i:ver) mx=max(mx, i);
    for(int i = 0; i < ver.size(); i++)
        if(ver[i]==u)
            ver.erase(ver.begin()+i);
    bool vis[nx];
    for(int i = 0; i <= mx; i++)
        vis[i]=0;
    vector<int> tmp;
    while(true)
    {
        int v=-1;
        for(int i:ver)
        {
            if(!vis[i])
            {
                v=i;
                vis[v]=1;
                break;
            }
        }
        if(v==-1) break;
        tmp.clear();
        tmp.emplace_back(v);
        for(int i:ver)
        {
            if(vis[i]) continue;
            if(Query(v, i, u)!=u)
                tmp.emplace_back(i), vis[i]=1;
        }
        tmp.emplace_back(u);
        dfs(u, tmp);
    }
}
void Solve(int n)
{
    vector<int> res;
    res.clear();
    for(int i = 0; i < n; i++)
        res.emplace_back(i);
    dfs(-1, res);
}
// int main()
// {
//     solve(5);
// }

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