oj.uz

Submission #923271

# Submission time Handle Problem Language Result Execution time Memory
923271 2024-02-07T04:30:22 Z MinhAnhnd Speedrun (RMI21_speedrun) C++14
0 / 100
 132 ms 920 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);
    }
}

void speedrun(int subtask, int N, int start) { /* your solution here */

}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 864 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 920 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 856 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 864 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 872 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -