제출 #375101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375101		wiwiho	Meetings (JOI19_meetings)	C++14	29 / 100	3068 ms	1680 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<vector<int>> anc;

bool comp(int a, int b){
    return anc[a].size() < anc[b].size();
}

void ans(int u, int v){
    if(u > v) swap(u, v);
    //cerr << u << " " << v << "\n";
    Bridge(u, v);
}

void Solve(int n){
    
    vector<int> dpt(n);
    anc.resize(n, vector<int>(1));
    anc[0].clear();

    for(int i = 1; i < n; i++){
        for(int j = i + 1; j < n; j++){
            int r = Query(0, i, j);
            if(r != i) anc[i].eb(r);
            if(r != j) anc[j].eb(r);
        }
    }

    vector<int> tmp(n);
    for(int i = 0; i < n; i++){
        tmp[i] = i;
        sort(iter(anc[i]));
        anc[i].resize(unique(iter(anc[i])) - anc[i].begin());
        dpt[i] = anc[i].size();
        //cerr << i << "  ";
        //printv(anc[i], cerr);
    }
    sort(iter(tmp), comp);

    for(int i : tmp){
        if(i == 0) continue;
        int mn = 0;
        for(int j : anc[i]){
            if(dpt[j] > dpt[mn]) mn = j;
        }
        ans(i, mn);
    }

}

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