Submission #934888

#	Time	Username	Problem	Language	Result	Execution time	Memory
934888		Darren0724	Meetings (JOI19_meetings)	C++17	100 / 100	835 ms	3184 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
const int N=2005;
int n;
void ans(int a,int b){
    if(a>b)swap(a,b);
    Bridge(a,b);
}
void dfs(int k,vector<int> &r){
    int sz=r.size();
    if(sz==0)return;
    int k1=r[rnd()%sz];
    vector<int> rec(n),adj[n];
    vector<int> path;
    for(int j:r){
        if(j==k1)continue;
        int lca=Query(k,k1,j);
        if(lca==j){
            rec[j]=1;
            path.push_back(j);
        }
        else{
            adj[lca].push_back(j);
        }
    }
    sort(path.begin(),path.end(),[&](int a,int b){return Query(k,a,b)==a;});
    path.push_back(k1);
    int last=k;
    for(int j:path){
        ans(last,j);
        last=j;
    }
    for(int j:path){
        dfs(j,adj[j]);
    }
    dfs(k,adj[k]);
}
void Solve(int n1) {
    n=n1;
    int k=rnd()%n;
    vector<int> t;
    for(int i=0;i<n;i++){
        if(i!=k)t.push_back(i);
    }
    dfs(k,t);
}

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