oj.uz

Submission #1014068

# Submission time Handle Problem Language Result Execution time Memory
1014068 2024-07-04T10:21:49 Z thangdz2k7 Meetings (JOI19_meetings) C++17
0 / 100
 21 ms 676 KB 
#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd

long long Rand(long long l, long long h) {
    assert(l <= h);
    return l + rd() * 1LL * rd() % (h - l + 1);
}

void cen(vector <int> &cur){
    int n = cur.size(); if (n == 1) return;

    int root = cur[Rand(0, n - 1)];
    vector <vector <int>> sub;
    int sz = 0;
    for (auto u : cur){
        if (u == root) continue;
        bool used = false;
        for (int i = 0; i < sz; ++ i){
            int par = sub[i][0];
            int lca = Query(root, par, u);
            if (lca == root) continue;
            sub[i].push_back(u);
            if (lca == u) swap(sub[i][sub[i].size() - 1], sub[i][0]);
            used = true;
        }
        if (!used) {
            sub.push_back({u});
            ++ sz;
        }
    }

    for (int i = 0; i < sz; ++ i){
        Bridge(root, sub[i][0]);
        cen(sub[i]);
    }
}

void Solve(int N){
    vector <int> cur = {};
    for (int i = 0; i < N; ++ i) cur.push_back(i);
    cen(cur);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 676 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -