Submission #1235913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235913		repsak	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	42 ms	1188 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// void dfs2(int u, vector<int>& visited, int team, vector<int>& C, vector<vector<int>>& adj){
//     if(team == -2) team = C[u];
//     if(visited[u]) return;
//     visited[u] = 1;

//     for(auto v : adj[u]){
//         if(C[v] != team) continue; 
//         dfs2(u, visited, team, C, adj);
//     }
// }

// int amountOfColors(int u, int N, int inc, vector<int> C, vector<vector<int>>& adj){
//     C[u] = inc;

//     int amount = 0;
//     vector<int> visited(N);

//     for(int i = 0; i < N; i++){
//         if(visited[i]) continue;
//         amount++;
//         dfs2(u, visited, -2, C, adj);
//     }

//     return amount;
// }   

void color(int u, int parent, int N, vector<int>& found, vector<vector<int>>& adj){
    
    
    int inc = 0;
    while(true){
        vector<int> C(N, inc);
        C[u] = -1;
        C[parent] = inc;

        int amount = perform_experiment(C);
        if(amount == 1){
            found[u] = inc;
            break;
        }
        inc++;
    }
    return;
}

void dfs(int u, int N, vector<int>& visited, vector<vector<int>>& adj, vector<int>& found){

    for(auto v : adj[u]){
        if(visited[v]) continue;
        color(v, u, N, found, adj);
        visited[v] = 1;
        dfs(v, N,  visited, adj, found);
    }

}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    vector<int> G(N, 0);

    if(N == 2){
        
        for(int i = 0; i < N; i++){
            
            vector<int> E = {-1, i};
            int x = perform_experiment(E);
            
            if(x == 1){
                G[0] = i;
            }
            
            vector<int> F = {i, -1};
            x = perform_experiment(F);

            if(x == 1){
                G[1] = i;
            }
        }
        
        return G;
    }

    vector<vector<int>> adj(N); 
    for(int i = 0; i < X.size(); i++){
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }   

    vector<int> found(N);
    vector<int> visited(N);

    dfs(0, N, visited, adj, found);

    return found;
}

// #include "grader.cpp"

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36