Submission #1125624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125624		OI_Account	Meetings (JOI19_meetings)	C++20	29 / 100	1265 ms	780 KiB

meetings

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

const int N = 2000;

int n, cnt[N + 10], par[N + 10];
vector<int> vec[N + 10];

void write(int u, int v) {
    //cout << "write" << u << ' ' << v << endl;
    u--, v--;
    Bridge(min(u, v), max(u, v));
}

int get(int u, int v, int w) {
    return Query(u - 1, v - 1, w - 1) + 1;
}

void add(int u, int v) {
    //cout << u << ' ' << v << endl;
    vec[u].push_back(v);
    cnt[v]++;
}

void init() {
    for (int i = 2; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            int k = get(1, i, j);
            //cout << i << ' ' << j << " -> " << k << endl;
            if (k == i)
                add(i, j);
            else if (k == j)
                add(j, i);
        }
    for (int i = 1; i <= 50'000; i++)
        get(1, 2, 3);
    fill(par + 2, par + n + 1, 1);
}

bool check() {
    //cout << "Come " << endl;
    vector<int> x;
    for (int i = 2; i <= n; i++)
        if (cnt[i] == 0) {
            x.push_back(i);
            cnt[i] = -1;
            //cout << i << ' ' << par[i] << endl;
        }
    for (auto u: x)
        for (auto v: vec[u]) {
            cnt[v]--;
            par[v] = u;
        }
    return x.size() != 0;
}

void writeOutput() {
    //cout << "alo " << endl; 
    for (int i = 2; i <= n; i++)
        write(par[i], i);
}

void solve() {
    init();
    while (check())
        ;
    writeOutput();
}

void Solve(int N) {
    n = N;
    solve();
}

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