oj.uz

Submission #851105

# Submission time Handle Problem Language Result Execution time Memory
851105 2023-09-18T14:01:47 Z 1zaid1 Meetings (JOI19_meetings) C++17
0 / 100
 510 ms 1112 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 mt(time(0));
const int M = 2005;
vector<int> sub[M];
int p[M];
void solve(int a) {
    vector<int> v;
    swap(v, sub[a]);
    int n = v.size();
    if (!n) return;

    int b = v[0];
    vector<int> nxt = {a, b};
    for (int i:v) {
        if (i == a || i == b) continue;

        int x = Query(a, b, i);
        if (x == i) nxt.push_back(i);
        else sub[x].push_back(i), p[i] = x;
    }

    sort(nxt.begin(), nxt.end(), [a](int x, int y) {
        if (x == a) return true;
        if (y == a) return false;
        return Query(a, x, y) == x;
    });

    for (int i = 1; i < nxt.size(); i++) p[nxt[i]] = nxt[i-1];
    for (int i:nxt) solve(i);
}

void Solve(int n) {
    vector<int> v;
    int m = mt()%n;
    for (int i = 0; i < n; i++) if (i != m) v.push_back(i);
    sort(v.begin(), v.end(), [](int a, int b) {return mt()%2;});
    sub[m] = v;
    p[m] = m;
    solve(m);
    for (int i = 0; i < n; i++) {
        if (i != p[i]) Bridge(min(p[i], i), max(p[i], i));
    }
}

Compilation message

meetings.cpp: In function 'void solve(int)':
meetings.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 1; i < nxt.size(); i++) p[nxt[i]] = nxt[i-1];
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 724 KB Output is correct
2 Correct 250 ms 600 KB Output is correct
3 Correct 250 ms 724 KB Output is correct
4 Correct 231 ms 732 KB Output is correct
5 Correct 190 ms 600 KB Output is correct
6 Correct 184 ms 600 KB Output is correct
7 Correct 394 ms 740 KB Output is correct
8 Correct 505 ms 980 KB Output is correct
9 Correct 479 ms 780 KB Output is correct
10 Correct 476 ms 852 KB Output is correct
11 Correct 510 ms 760 KB Output is correct
12 Correct 320 ms 856 KB Output is correct
13 Correct 143 ms 740 KB Output is correct
14 Runtime error 2 ms 1112 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -