oj.uz

Submission #374974

# Submission time Handle Problem Language Result Execution time Memory
374974 2021-03-08T17:33:43 Z BartolM Meetings (JOI19_meetings) C++17
29 / 100
 385 ms 748 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2005;

int n, uk;

#define DEBUG 0
void upit(int x, int y) {
    #if DEBUG
        printf("%d <-> %d\n", x, y);
    #endif
    Bridge(min(x, y), max(x, y));
}

void rek(vector <int> v) {
    if (v.size()==1) return;

    random_shuffle(v.begin(), v.end());
    int l=v[0], r=v[1];
    vector <int> v_l, v_r;
    v_l.pb(l); v_r.pb(r);
    for (int x:v) {
        if (x==l || x==r) continue;
        int y=Query(x, l, r);
        if (y==l) v_l.pb(x);
        else if (y==r) v_r.pb(x);
        else {
            if (v_l.size()<v_r.size()) {
                v_l.pb(x);
                l=y;
                if (y!=x) v_l.pb(y);
            }
            else {
                v_r.pb(x);
                r=y;
                if (y!=x) v_r.pb(y);
            }
        }
    }
    upit(l, r);
    rek(v_l); rek(v_r);
}

void Solve(int nn) {
    n=nn;
    srand(time(0));
    vector <int> poc;
    for (int i=0; i<n; ++i) poc.pb(i);
    rek(poc);
}
/*
5
0 1
0 2
1 3
1 4
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 8 ms 364 KB Output is correct
28 Correct 7 ms 364 KB Output is correct
29 Correct 8 ms 364 KB Output is correct
30 Correct 7 ms 364 KB Output is correct
31 Correct 8 ms 384 KB Output is correct
32 Correct 8 ms 376 KB Output is correct
33 Correct 10 ms 364 KB Output is correct
34 Correct 9 ms 492 KB Output is correct
35 Correct 9 ms 492 KB Output is correct
36 Correct 8 ms 364 KB Output is correct
37 Correct 8 ms 364 KB Output is correct
38 Correct 8 ms 364 KB Output is correct
39 Correct 7 ms 364 KB Output is correct

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 385 ms 748 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -