oj.uz

Submission #538348

# Submission time Handle Problem Language Result Execution time Memory
538348 2022-03-16T15:55:47 Z dantoh000 Speedrun (RMI21_speedrun) C++14
100 / 100
 125 ms 900 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
vector<int> G[1005];
int pa[1005];
int pre[1005];
int last = 0;
void include(int u, int v, int w){
    //printf("including %d %d %d\n",u,v,w);
    for (int j = 1; j <= 10; j++){
        if ((v>>(j-1))&1) setHint(u,j,1);
    }

    for (int j = 11; j <= 20; j++){
        if ((w>>(j-11))&1) setHint(u,j,1);
    }
}
void setup(int u, int p){
    pre[last] = u;
    if (last){

        include(last, pa[last], u);
    }
    pa[u] = p;
    last = u;
    for (auto v : G[u]){
        if (v == p) continue;
        setup(v,u);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    for (int i = 1; i < N; i++){
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    setup(1, 0);
    if (last) include(last, pa[last], 0);
}
int n;
ii proc(int u){
    ii x = ii(0,0);
    for (int i = 1; i <= 10; i++){
        if (getHint(i)) x.first += (1<<(i-1));
    }
    for (int i = 11; i <= 20; i++){
        if (getHint(i)) x.second += (1<<(i-11));
    }
    return x;
}

int getroot(int x){
    while (x){
        ii D = proc(x);
        //printf("%d --> %d\n",x,D.first);
        if (D.first){
            goTo(D.first);
            x = D.first;
        }
        else break;
    }
    return x;
}
int togoto = 0;
void dfs(int u, int p){
    ii D = proc(u);
    //printf("at %d: %d %d\n",u,D.first,D.second);

    if (D.second && goTo(D.second)){
        dfs(D.second, u);
        goTo(u);
    }
    else{
        togoto = D.second;
        return;
    }
    while (true){
        //printf("done with %d, checking %d\n",u,togoto);
        if (togoto && goTo(togoto)){
            dfs(togoto, u);
            goTo(u);
        }
        else break;
    }

}



void speedrun(int subtask, int N, int start) { /* your solution here */
    n = N;
    int root = getroot(start);
    //printf("%d ",root);
    dfs(root,0);

}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 712 KB Output is correct
2 Correct 78 ms 848 KB Output is correct
3 Correct 68 ms 724 KB Output is correct
4 Correct 82 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 760 KB Output is correct
2 Correct 96 ms 724 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 760 KB Output is correct
2 Correct 106 ms 900 KB Output is correct
3 Correct 105 ms 824 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 724 KB Output is correct
2 Correct 125 ms 736 KB Output is correct
3 Correct 81 ms 752 KB Output is correct
4 Correct 95 ms 720 KB Output is correct
5 Correct 91 ms 704 KB Output is correct
6 Correct 89 ms 676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 744 KB Output is correct
2 Correct 112 ms 768 KB Output is correct
3 Correct 95 ms 744 KB Output is correct
4 Correct 93 ms 788 KB Output is correct
5 Correct 92 ms 672 KB Output is correct
6 Correct 112 ms 672 KB Output is correct
7 Correct 87 ms 684 KB Output is correct