Submission #375097

#	Time	Username	Problem	Language	Result	Execution time	Memory
375097		wiwiho	Meetings (JOI19_meetings)	C++14	0 / 100	3066 ms	1144 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
 
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
 
using namespace std;
 
typedef long long ll;  

vector<set<int>> g;

void addEdge(int a, int b){
    g[a].insert(b);
    g[b].insert(a);
}

void insertEdge(int a, int b, int v){
    g[a].erase(b);
    g[b].erase(a);
    addEdge(a, v);
    addEdge(b, v);
}

vector<int> sz, mx;
vector<int> tv;
vector<bool> del;

void dfs(int now, int p){
    sz[now] = 1;
    tv.eb(now);
    mx[now] = 0;
    for(int i : g[now]){
        if(i == p || del[i]) continue;
        dfs(i, now);
        sz[now] += sz[i];
        mx[now] = max(mx[now], sz[i]);
    }
}

void calc(int now, int qry){
    tv.clear();
    dfs(now, now);

    if(tv.size() == 1){
        addEdge(now, qry);
        //cerr << qry << " add " << now << "\n";
        return;
    }

    int gv = now;
    for(int i : tv){
        if(mx[i] <= sz[now] / 2 && sz[now] - sz[i] <= sz[now] / 2) gv = i;
    }
    //cerr << "test " << now << " " << gv << "\n";
    del[gv] = true;

    for(int i : g[gv]){
        if(del[i]) continue;
        int r = Query(i, gv, qry);
        if(r == qry){
            insertEdge(i, gv, qry);
            //cerr << qry << " insert " << i << " " << gv << "\n";
            return;
        }
        else if(r == i){
            calc(i, qry);
            return;
        }
    }
    addEdge(gv, qry);
    //cerr << qry << " gv " << gv << "\n";
}

void Solve(int n){
    
    sz.resize(n);
    mx.resize(n);
    del.resize(n);
    g.resize(n);

    addEdge(0, 1);

    for(int i = 2; i < n; i++){
        fill(iter(del), false);
        calc(0, i);
    }

//    for(int i = 0; i < n; i++){
//        cerr << i << "  ";
//        printv(g[i], cerr);
//    }

    for(int i = 0; i < n; i++){
        for(int j : g[i]){
            if(i < j){
                //cerr << i << " " << j << "\n";
                Bridge(i, j);
            }
        }
    }

}

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