Submission #126906

#	Time	Username	Problem	Language	Result	Execution time	Memory
126906		Osama_Alkhodairy	Meetings (JOI19_meetings)	C++17	100 / 100	1819 ms	1292 KiB

meetings

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

const int maxn = 2001;

int n, dep[maxn];
vector <int> p, pans, v[maxn];
int asked = 0;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void dfsz(int node){
    for(auto &i : v[node]){
        dep[i] = dep[node] + 1;
        dfsz(i);
    }
}
int LCA(int a, int b){
    if(a == b) return a;
    if(a == 0 || b == 0) return 0;
    return Query(0, a, b);
}
void solve(vector <int> a){
    if(a.size() <= 1) return;
    shuffle(a.begin(), a.end(), rng);
    int leaf = -1;
    for(auto &i : a){
        leaf = i;
        break;
    }
    if(leaf == -1) return;
    vector <int> q(n + 1);
    vector <int> anc;
    for(auto &i : a){
        q[i] = LCA(i, leaf);
        anc.push_back(q[i]);
    }
    sort(anc.begin(), anc.end());
    anc.resize(unique(anc.begin(), anc.end()) - anc.begin());
    sort(anc.begin(), anc.end(), [&](int a, int b){
        return LCA(a, b) == a;
    });
    for(int i = 1 ; i < (int)anc.size() ; i++)
        pans[anc[i]] = anc[i - 1];
    for(auto &i : anc){
        vector <int> c;
        for(auto &j : a){
            if(q[j] == i && i != j){
                c.push_back(j);
                pans[j] = i;
            }
        }
        solve(c);
    }
}
void bridge(int a, int b){
    if(b < a) swap(a, b);
    Bridge(a, b);
}
void go(){
    asked = 0;
    for(int i = 0 ; i < n ; i++){
        v[i].clear();
    }
    p.assign(n + 1, -1);
    int root = -1;
    for(int i = 0 ; i < n ; i++){
        if(p[i] == -1) root = i;
        else v[p[i]].push_back(i);
    }
    dfsz(root);
    pans.assign(n + 1, -1);
    vector <int> all;
    for(int i = 0 ; i < n ; i++){
        all.push_back(i);
    }
    solve(all);
    for(int i = 1 ; i < n ; i++){
        bridge(i, pans[i]);
    }
}
void Solve(int N) {
    n = N;
    go();
}

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