oj.uz

Submission #1115094

# Submission time Handle Problem Language Result Execution time Memory
1115094 2024-11-20T03:41:55 Z rqi Sphinx's Riddle (IOI24_sphinx) C++17
10 / 100
 425 ms 1716 KB 
#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;

#define sz(x) int((x).size())
#define pb push_back
#define mp make_pair
#define f first
#define s second

struct DSU{
    vi e;
    void init(int N){
        e = vi(N, -1);
    }
    int get(int x){
        if(e[x] == -1) return x;
        e[x] = get(e[x]);
        return e[x];
    }
    bool unite(int x, int y){
        x = get(x);
        y = get(y);
        if(x == y) return false;
        if(-e[x] < -e[y]) swap(x, y);
        e[y] = x;
        return true;
    }
};

const int mx = 255;
int N;
vpi eds;
vi adj[mx];

int my_experiment(vi E){
    DSU dsu;
    dsu.init(N);
    for(auto [a, b]: eds){
        if(E[a] == N && E[b] == N){
            dsu.unite(a, b);
        }
    }



    int neg_cnt = 0;
    for(int i = 0; i < N; i++){
        if(E[i] == N && dsu.get(i) == i){
            neg_cnt++;
        }
    }

    int query_res = perform_experiment(E);
    return query_res - neg_cnt;
}

vi find_colours(int _N, vi X, vi Y) {
    N = _N;
    int M = sz(X);
    for(int i = 0; i < M; i++){
        eds.pb(mp(X[i], Y[i]));
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }

    vi ans(N, -1);
    for(int i = 0; i < N; i++){
        int other_node = adj[i][0];
        for(int j = 0; j < N; j++){
            cerr << "nodes: " << i << " " << other_node << "\n";
            vi E(N, N);
            E[i] = -1;
            E[other_node] = j;
            int query_res = my_experiment(E);
            if(query_res == 1){
                ans[i] = j;
                break;
            }
        }
    }

    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 6

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 3
3 Correct 2 ms 336 KB #experiments: 3
4 Correct 1 ms 336 KB #experiments: 4

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 6
2 Correct 1 ms 336 KB #experiments: 2
3 Correct 1 ms 336 KB #experiments: 3
4 Correct 2 ms 336 KB #experiments: 3
5 Correct 1 ms 336 KB #experiments: 4
6 Correct 36 ms 704 KB #experiments: 1250
7 Correct 27 ms 456 KB #experiments: 785
8 Correct 56 ms 508 KB #experiments: 1613
9 Correct 40 ms 456 KB #experiments: 1353
10 Correct 40 ms 336 KB #experiments: 1138
11 Correct 30 ms 708 KB #experiments: 978
12 Correct 42 ms 456 KB #experiments: 1278
13 Correct 52 ms 584 KB #experiments: 1275
14 Correct 32 ms 676 KB #experiments: 750
15 Correct 33 ms 336 KB #experiments: 920
16 Correct 50 ms 504 KB #experiments: 1361
17 Correct 47 ms 1008 KB #experiments: 1109
18 Correct 63 ms 680 KB #experiments: 1506
19 Correct 45 ms 840 KB #experiments: 1280
20 Correct 54 ms 336 KB #experiments: 1376
21 Correct 46 ms 592 KB #experiments: 1275
22 Correct 8 ms 336 KB #experiments: 196
23 Correct 7 ms 348 KB #experiments: 150
24 Correct 10 ms 336 KB #experiments: 312
25 Correct 25 ms 336 KB #experiments: 650
26 Correct 30 ms 336 KB #experiments: 966
27 Correct 31 ms 336 KB #experiments: 1071
28 Correct 38 ms 588 KB #experiments: 1208
29 Correct 40 ms 592 KB #experiments: 1179
30 Correct 40 ms 592 KB #experiments: 1209
31 Correct 44 ms 508 KB #experiments: 1187
32 Correct 50 ms 764 KB #experiments: 1417
33 Correct 42 ms 336 KB #experiments: 1470
34 Correct 40 ms 584 KB #experiments: 1275

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 3
3 Correct 2 ms 336 KB #experiments: 3
4 Correct 1 ms 336 KB #experiments: 4
5 Correct 36 ms 704 KB #experiments: 1250
6 Correct 27 ms 456 KB #experiments: 785
7 Correct 56 ms 508 KB #experiments: 1613
8 Correct 40 ms 456 KB #experiments: 1353
9 Correct 40 ms 336 KB #experiments: 1138
10 Correct 30 ms 708 KB #experiments: 978
11 Correct 42 ms 456 KB #experiments: 1278
12 Correct 52 ms 584 KB #experiments: 1275
13 Incorrect 117 ms 584 KB #experiments reached 2751
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 3
3 Correct 2 ms 336 KB #experiments: 3
4 Correct 1 ms 336 KB #experiments: 4
5 Correct 32 ms 676 KB #experiments: 750
6 Correct 33 ms 336 KB #experiments: 920
7 Correct 50 ms 504 KB #experiments: 1361
8 Correct 47 ms 1008 KB #experiments: 1109
9 Correct 63 ms 680 KB #experiments: 1506
10 Correct 45 ms 840 KB #experiments: 1280
11 Correct 54 ms 336 KB #experiments: 1376
12 Correct 46 ms 592 KB #experiments: 1275
13 Incorrect 425 ms 1716 KB #experiments reached 2751
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 6
2 Correct 1 ms 336 KB #experiments: 2
3 Correct 1 ms 336 KB #experiments: 3
4 Correct 2 ms 336 KB #experiments: 3
5 Correct 1 ms 336 KB #experiments: 4
6 Correct 36 ms 704 KB #experiments: 1250
7 Correct 27 ms 456 KB #experiments: 785
8 Correct 56 ms 508 KB #experiments: 1613
9 Correct 40 ms 456 KB #experiments: 1353
10 Correct 40 ms 336 KB #experiments: 1138
11 Correct 30 ms 708 KB #experiments: 978
12 Correct 42 ms 456 KB #experiments: 1278
13 Correct 52 ms 584 KB #experiments: 1275
14 Correct 32 ms 676 KB #experiments: 750
15 Correct 33 ms 336 KB #experiments: 920
16 Correct 50 ms 504 KB #experiments: 1361
17 Correct 47 ms 1008 KB #experiments: 1109
18 Correct 63 ms 680 KB #experiments: 1506
19 Correct 45 ms 840 KB #experiments: 1280
20 Correct 54 ms 336 KB #experiments: 1376
21 Correct 46 ms 592 KB #experiments: 1275
22 Correct 8 ms 336 KB #experiments: 196
23 Correct 7 ms 348 KB #experiments: 150
24 Correct 10 ms 336 KB #experiments: 312
25 Correct 25 ms 336 KB #experiments: 650
26 Correct 30 ms 336 KB #experiments: 966
27 Correct 31 ms 336 KB #experiments: 1071
28 Correct 38 ms 588 KB #experiments: 1208
29 Correct 40 ms 592 KB #experiments: 1179
30 Correct 40 ms 592 KB #experiments: 1209
31 Correct 44 ms 508 KB #experiments: 1187
32 Correct 50 ms 764 KB #experiments: 1417
33 Correct 42 ms 336 KB #experiments: 1470
34 Correct 40 ms 584 KB #experiments: 1275
35 Incorrect 117 ms 584 KB #experiments reached 2751
36 Halted 0 ms 0 KB -