Submission #522301

#	Time	Username	Problem	Language	Result	Execution time	Memory
522301		phamhoanghiep	Meetings (JOI19_meetings)	C++14	100 / 100	671 ms	4800 KiB

meetings

#include<bits/stdc++.h>
#include"meetings.h"
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
map<iii,int> M;
mt19937 rng(1);
int Rand(int l, int r) {
    return rng()%(r-l+1)+l;
}
const int maxn=100005;
vector<int> vt;
vector<ii> edges;
vector<int> path;
vector<int> subtree[maxn];
int belong[maxn];
int _N;
int st=0;
/*
int Query(int u, int v, int w) {
    cout<<"query "<<u<<" "<<v<<" "<<w<<endl;
    int x;
    cin>>x;
    return x;
}
void Bridge(int u, int v) {
    cout<<"edge "<<u<<" "<<v<<endl;
}
*/
int ask(int u, int v, int w) {
    if(v>w) swap(v,w);
    if(u>v) swap(u,v);
    if(v>w) swap(v,w);
    if(M[iii(u,ii(v,w))]) return M[iii(u,ii(v,w))];
    else return M[iii(u,ii(v,w))]=Query(u,v,w);
}
void push(vector<int>& vec, int pos, int val) {
    // right before pos (between pos and pos-1)
    //cout<<"push "<<pos<<" "<<val<<endl;
    vector<int> nw;
    for(int i=0 ; i<(int)vec.size() ; i++) {
        if(i==pos) nw.push_back(val);
        nw.push_back(vec[i]);
    }
    vec.swap(nw);
}
void do_path() {
    //cout<<"path: "<<endl;
    //for(int u: path) cout<<u<<' ';
    //cout<<endl;
    vector<int> res;
    res.push_back(path[0]);
    res.push_back(path[1]);
    for(int i=2 ; i<(int)path.size() ; i++) {
        // find for path(i), current inside res: i
        if(ask(res[0],res[1],path[i])==res[0]) push(res,0,path[i]);
        else if(ask(res[i-1],res[i-2],path[i])==res[i-1]) res.push_back(path[i]);
        else {
            int l=0;
            int r=i-2;
            while(l<r) {
                //cout<<"l r "<<l<<" "<<r<<endl;
                int mid=(l+r+1)/2;
                if(ask(res[mid],res[mid+1],path[i])==res[mid]) r=mid-1;
                else l=mid;
            }
            //cout<<"l = "<<l<<endl;
            push(res,l+1,path[i]);
        }
        //cout<<"res: "<<endl;
        //for(int u: res) cout<<u<<' ';
        //cout<<endl;
    }
    //cout<<"res: "<<endl;
    //for(int u: res) cout<<u<<' ';
    //cout<<endl;
    for(int i=0 ; i<(int)res.size()-1 ; i++) {
        edges.push_back(ii(res[i],res[i+1]));
    }
}
void do_things(vector<int> &nodes) {
    //cout<<"nodes: "<<endl;
    //for(int u: nodes) cout<<u<<' ';
    //cout<<endl;
    if(nodes.size()<2) {
        return;
    }
    if(nodes.size()==2) {
        edges.push_back(ii(nodes[0],nodes[1]));
        return;
    }
    for(int i=0 ; i<_N ; i++) belong[i]=0;
    path.clear();
    int sz=nodes.size();
    int root1=Rand(0,sz-1);
    int root2=Rand(0,sz-1);
    while(root2==root1) root2=Rand(0,sz-1);
    root1=nodes[root1]; root2=nodes[root2];
    int stt=st+1;
    belong[root1]=st+1;
    belong[root2]=st+2;
    subtree[st+1].push_back(root1);
    //cout<<"subtree "<<st+1<<".push_back "<<root1<<endl;
    subtree[st+2].push_back(root2);
    //cout<<"subtree "<<st+2<<".push_back "<<root2<<endl;
    st+=2;
    path.push_back(root1); path.push_back(root2);
    for(int u: nodes) {
        if(u==root1||u==root2) continue;
        int x=ask(root1,root2,u);
        if(!belong[x]) {
            belong[x]=++st;
            path.push_back(x);
        }
        subtree[belong[x]].push_back(u);
        //cout<<"subtree "<<belong[x]<<".push_back "<<u<<endl;
    }
    int en=st;
    sort(path.begin(),path.end());
    auto it=unique(path.begin(),path.end());
    path.resize(distance(path.begin(),it));
    do_path();
    for(int i=stt ; i<=en ; i++) {
        sort(subtree[i].begin(),subtree[i].end());
        auto it=unique(subtree[i].begin(),subtree[i].end());
        subtree[i].resize(distance(subtree[i].begin(),it));
        //cout<<"i = "<<i<<endl;
        do_things(subtree[i]);
    }
}
void Solve(int N) {
    _N=N;
    for(int i=0 ; i<N ; i++) vt.push_back(i);
    do_things(vt);
    for(int i=0 ; i<(int)edges.size() ; i++) {
        if(edges[i].first>edges[i].second) swap(edges[i].first,edges[i].second);
    }
    sort(edges.begin(),edges.end());
    for(int i=0 ; i<(int)edges.size() ; i++) {
        //cout<<"edges "<<i<<" = "<<edges[i].first<<" "<<edges[i].second<<endl;
        if(!i||edges[i]!=edges[i-1]) Bridge(edges[i].first,edges[i].second);
    }
    // base 0

}
/*
signed main() {
    int N;
    cin>>N;
    Solve(N);
}
*/

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