oj.uz

Submission #933619

# Submission time Handle Problem Language Result Execution time Memory
933619 2024-02-26T01:30:24 Z vjudge1 Speedrun (RMI21_speedrun) C++17
21 / 100
 23 ms 2160 KB 
#include <bits/stdc++.h>
#include "speedrun.h"
#define endl '\n'
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define fore(i,l,r) for(int i = l; i < r;i++)
#define forex(i,r,l) for(int i = r; i>= l;i--)
#define fo(i,n) fore(i,0,n)
#define ffo(i,n) forex(i,n-1,0)
#define lsb(x) x&(-x)
using namespace std;
using ii = pair<int,int>;using ll = long long; using ull = unsigned long long;
using vi = vector<int>;
// const int maxN = 30;
// int hintlen,mistart;vi res;
// int number[maxN];
// void setHintLen(int sz){
//     hintlen=sz;
// }
// void setHint(int a, int b, bool cl, bool donde=0){if(donde==0)return;
//     if(number[a]&1<<b == cl)return;
//     assert(donde==1);
//     number[a]^=1<<b;
// }
// int getLength(){return hintlen;}
// bool getHint(int j ){
//     // cout << mistart << " " << j << endl; cout.flush();
//     return (number[mistart]&(1<<j) ? 1 : 0 );
// }
// bool goTo(int j){
//     if(number[mistart]&(1<<j) == 0)return false;
//     res.pb(j);
//     mistart=j;
//     return true;
// }
void assignHints(int subtask, int N , int A[], int B[]){
    if(subtask>=2)setHintLen(20);
    else setHintLen(N);
    vi cont(N+2, 0),graph[N+2];
    fore(i,1,N){graph[A[i]].pb(B[i]); graph[B[i]].pb(A[i]);
        if(subtask == 1){
            setHint(A[i], B[i], 1);
            setHint(B[i], A[i], 1);
        }else if(subtask == 2){
            cont[A[i]]++;cont[B[i]]++;
        }
    }
    if(subtask==2){
        if(N==1)return;
        fore(i,1,N+1){
            if(cont[i]>1){
                setHint(i, 1, 1);
                setHint(i, 2, 1);
            }else{// no es el centro
                setHint(i, 1, 1);
            }
        }
    }else if (subtask == 3){
        fore(i,1,N){bool ini = 1;
            for(int v : graph[i]){
                fo(j,10){
                    int k = j+(!ini ? 10 : 0 );
                    setHint(i, k, (v&(1<<k) ? 1 : 0));
                }
                ini = 0;
            }
        }
    }
}
vector<vector<int>> graph;
vector<bool> precalc, vis;int szn;
void dfs(int nodo, int donde = 0){
    if(!precalc[nodo]){
        precalc[nodo] = 1;
        fore(i,1,szn+1){
            if(getHint(i)){
                graph[nodo].pb(i);
            }
        }
    }
    for(int v : graph[nodo]){
        if(!vis[v]){
            vis[v]=1;
            goTo(v);dfs(v, nodo);
        }
    }
    if(donde == 0)return ;
    goTo(donde);
}
void speedrun(int subtask, int N, int start){if(N==1)return;
    vis.resize(N+2,0);precalc.resize(N+2,0);szn=N;
    graph.resize(N+2);getLength();
    if(subtask == 2){
        int num = 0;
        fore(i,1,N+1){
            if(getHint(i))num++;
        }
        if(num>=2){
            fore(i,1,N+1){if(i==start)continue;
                goTo(i);if(i==N)return;
                goTo(start);
            }
        }else{
            int p = 0;
            fore(i,1,N+1)if(i!=start and goTo(i)){p=i;break;}
            fore(i,1,N+1){if(i==p || i==start) continue;
                goTo(i);if(i==N)return;
                goTo(p);
            }
        }
        return;
    }else if(subtask == 3 ){
        
        return;
    }
    vis[start] = 1;
    dfs(start);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1756 KB Output is correct
2 Correct 22 ms 2160 KB Output is correct
3 Correct 20 ms 1164 KB Output is correct
4 Correct 21 ms 2036 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1352 KB Invalid bit index for getHint
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 908 KB Invalid bit index for getHint
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 900 KB Invalid bit index for getHint
2 Halted 0 ms 0 KB -