oj.uz

Submission #923293

# Submission time Handle Problem Language Result Execution time Memory
923293 2024-02-07T05:13:50 Z MinhAnhnd Speedrun (RMI21_speedrun) C++14
0 / 100
 231 ms 968 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    bool leaf[N+1];
    bool visited[N+1];
    long parent[N+1];
    long first_val[N+1];
    long second_val[N+1];
    long depth[N+1];
    stack<long> tovisit;
    setHintLen(20);
    vector<long> adjlist[N+1];
    vector<long> leaves;
    for (int i = 1;i<=N;i++){
        leaf[i] = 1;
        parent[i] = 0;
        visited[i] = 0;
        first_val[i] = -1;
        second_val[i] = -1;
        depth [i]= 0;
    }

    //setHintLen(N);
    for(int i = 1;i<N;i++){
        adjlist[A[i]].push_back(B[i]);
        adjlist[B[i]].push_back(A[i]);
    }
    tovisit.push(1);
    depth[1] = 1;
    while(!tovisit.empty()){
        long current = tovisit.top();
        tovisit.pop();
        if(visited[current]) continue;
        visited[current]=1;

        for (auto i:adjlist[current]){
            if(!visited[i]){
                depth[i] = depth[current] + 1;
                leaf[current] = 0;
                parent[i] = current;
                tovisit.push(i);
            }
        }
    }
    for (int i = 1;i<=N;i++){
        if (leaf[i]){
            leaves.push_back(i);
        }
    }
    for (auto green: leaves){
        if (second_val[parent[green]]==-1) second_val[parent[green]] = green;
        long current = parent[green];
        while(current!=0){
            first_val[current] = parent[current];

            if (second_val[parent[current]]==-1) second_val[parent[current]] = current;

            current = parent[current];
        }
    }
    leaves.push_back(leaves[0]);
    for (long i = 1;i<(long)leaves.size();i++){
        long a = leaves[i-1];
        long b = leaves[i];
        long b_low = 0;
        while(depth[a]>depth[b]) a= parent[a];
        while(depth[a]<depth[b]) {b= parent[b];b_low=b;}
        while(a!=b){
            a= parent[a];
            b= parent[b];b_low=b;
        }
        first_val[leaves[i-1]] = b;
        second_val[leaves[i-1]] = b_low;
    }
    for (long i = 1;i<=N;i++){
        for (long j = 0;j<=9;j++) setHint(i,j+1,(first_val[i]>>j)&1);
        for (long j = 0;j<=9;j++) setHint(i,j+11,(second_val[i]>>j)&1);
    }
}

#define getData() for (long j = 0;j<=9;j++) first_val|=getHint(j+1)<<j; for (long j = 0;j<=9;j++) second_val|=getHint(j+11)<<j
void speedrun(int subtask, int N, int start) { /* your solution here */
    long first_val = 0;
    long second_val = 0;

    for (int i = 1;i<=N;i++){

    }

    getData();

    if (first_val!=0){
    bool go_up = goTo(first_val);
    long j = first_val;
    if (!go_up)  j = 0;
    while (!go_up){
        j++;
        go_up  = goTo(j);
    }
    getData();
    while(first_val!=0){
        goTo(first_val);
        getData();
    }
    }
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 856 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 968 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 856 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 231 ms 856 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 892 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -