Submission #522258

#	Time	Username	Problem	Language	Result	Execution time	Memory
522258		phamhoanghiep	Meetings (JOI19_meetings)	C++14	0 / 100	65 ms	600 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=2005;
    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)
        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) {
                    int mid=(l+r+1)/2;
                    if(ask(res[l],res[l+1],path[i])==res[l]) r=mid-1;
                    else l=mid;
                }
                push(res,l+1,path[i]);
            }
        }
        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;
        }
        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;
        }
        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<=st ; i++) {
            do_things(subtree[i]);
        }
    }
    void Solve(int 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() {
        cin>>N;
        Solve(N);
    }
    */
     

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