oj.uz

Submission #1115100

# Submission time Handle Problem Language Result Execution time Memory
1115100 2024-11-20T04:05:31 Z rqi Sphinx's Riddle (IOI24_sphinx) C++17
18 / 100
 12 ms 504 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);

    DSU dsu; dsu.init(N);
    for(int i = 0; i+1 < N; i++){
        vi E = vi(N, N);
        E[i] = E[i+1] = -1;
        int query_res = my_experiment(E);
        assert(query_res == 1 || query_res == 2);
        if(query_res == 1){
            dsu.unite(i, i+1);
        }
    }

    for(int i = 0; i < N; i++){
        ans[i] = dsu.get(i);
    }

    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #1
1.5 / 3.0

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

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Correct 1 ms 336 KB #experiments: 1
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 2 ms 336 KB Partially correct
7 Partially correct 2 ms 336 KB Partially correct
8 Partially correct 2 ms 336 KB Partially correct
9 Partially correct 2 ms 336 KB Partially correct
10 Partially correct 2 ms 336 KB Partially correct
11 Partially correct 2 ms 336 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 2 ms 336 KB Partially correct
14 Partially correct 2 ms 336 KB Partially correct
15 Incorrect 3 ms 336 KB Vertices 0 and 12 do have the same color, but they do not in returned answer
16 Halted 0 ms 0 KB -

Subtask #3
16.5 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 2 ms 336 KB Partially correct
6 Partially correct 2 ms 336 KB Partially correct
7 Partially correct 2 ms 336 KB Partially correct
8 Partially correct 2 ms 336 KB Partially correct
9 Partially correct 2 ms 336 KB Partially correct
10 Partially correct 2 ms 336 KB Partially correct
11 Partially correct 1 ms 336 KB Partially correct
12 Partially correct 2 ms 336 KB Partially correct
13 Partially correct 9 ms 336 KB Partially correct
14 Partially correct 9 ms 504 KB Partially correct
15 Partially correct 8 ms 336 KB Partially correct
16 Partially correct 9 ms 336 KB Partially correct
17 Partially correct 12 ms 336 KB Partially correct
18 Partially correct 9 ms 336 KB Partially correct
19 Partially correct 8 ms 336 KB Partially correct
20 Partially correct 12 ms 336 KB Partially correct
21 Partially correct 8 ms 336 KB Partially correct

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 2 ms 336 KB Partially correct
6 Incorrect 3 ms 336 KB Vertices 0 and 12 do have the same color, but they do not in returned answer
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Correct 1 ms 336 KB #experiments: 1
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 2 ms 336 KB Partially correct
7 Partially correct 2 ms 336 KB Partially correct
8 Partially correct 2 ms 336 KB Partially correct
9 Partially correct 2 ms 336 KB Partially correct
10 Partially correct 2 ms 336 KB Partially correct
11 Partially correct 2 ms 336 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 2 ms 336 KB Partially correct
14 Partially correct 2 ms 336 KB Partially correct
15 Incorrect 3 ms 336 KB Vertices 0 and 12 do have the same color, but they do not in returned answer
16 Halted 0 ms 0 KB -