Submission #260254

#	Time	Username	Problem	Language	Result	Execution time	Memory
260254		infinitepro	Meetings (JOI19_meetings)	C++17	29 / 100	3079 ms	5640 KiB

meetings

#include<bits/stdc++.h>
#include"meetings.h"
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

// holds nearest known children branch root
vvi B;

map<ii, int> csr;
int ask(int u, int v){
    if(u > v) swap(u, v);
    if(u == v || u == 0 || v == 0) cerr << "END!" << endl;
    if(csr.find({u, v}) == csr.end()){
        int k = Query(0, u, v);
        csr[{u, v}] = k;
    }
    return csr[{u, v}];
}

int doshit(int rt, int u){
    if(rt == u) return -7;

    bool set = false;
    for(auto &v : B[rt]){
        if(v == u){set = true; break;}

        int par = ask(u, v);
        if(par == rt) continue;
        set = true;

        if(par == v){
            doshit(v, u);
        }else if(par == u){
            doshit(u, v);
            v = u; 
        }else{
            doshit(par, u);
            doshit(par, v);
            v = par;
        }
        break;
    }
    if(!set) {B[rt].push_back(u); random_shuffle(all(B[rt]));}
    return 0;
}

void Solve(int N){
    srand(123456);

    B.resize(N+10);
    vi rem;
    for(int x = 1; x < N; x++)
        rem.push_back(x);
    random_shuffle(all(rem));

    while(rem.size() >= 2){
        int u = rem.back(); rem.pop_back();
        int v = rem.back(); rem.pop_back();
    
        int par = ask(u, v);
        if(doshit(par, u) == -7) rem.push_back(u);
        if(doshit(par, v) == -7) rem.push_back(v);

        // cerr << "For nodes: " << u << ", " << v << endl;
        // for(int u = 0; u < N; u++){
        //     cerr << u << " ::: ";
        //     for(auto v : B[u]) cerr << v << " ";
        //     cerr << endl;
        // }
        // cerr << "-----" << endl;
    }

    if(rem.size() == 1){
        int u = rem.back(); rem.pop_back();
        for(int x = 1; x < N; x++)
            if(x != u) rem.push_back(x);
        random_shuffle(all(rem));
        set<int> vviiss;

        bool done = false;
        while(rem.size()){
            int v = rem.back(); rem.pop_back();
            if(vviiss.find(v) != vviiss.end()) continue;

            int par = ask(u, v);
            if(doshit(par, u) == -7){
                queue<int> dpd; dpd.push(v);
                vviiss.insert(v);
                while(!dpd.empty()){
                    int z = dpd.front(); dpd.pop();
                    for(auto j : B[z]){
                        vviiss.insert(j);
                        dpd.push(j);
                    }
                }
            }else{
                done = true;
                // cerr << "For nodes: " << u << ", " << v << endl;
                // for(int u = 0; u < N; u++){
                //     cerr << u << " ::: ";
                //     for(auto v : B[u]) cerr << v << " ";
                //     cerr << endl;
                // }
                // cerr << "-----" << endl;
                break;
            }
        }

        if(!done){
            if(B[0].empty()) B[0].push_back(u);
            else{
                int v = B[0][0];
                B[0][0] = u;
                B[u].push_back(v);
            }
        }
    }

    for(int u = 0; u < N; u++)
        for(auto v : B[u]){
            if(u > v) Bridge(v, u);
            else Bridge(u, v);
        }
    return;
}

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