oj.uz

Submission #923326

# Submission time Handle Problem Language Result Execution time Memory
923326 2024-02-07T06:27:39 Z MinhAnhnd Speedrun (RMI21_speedrun) C++14
100 / 100
 131 ms 2408 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;



long order[1001];
bool sorter(long a,long b){
    return order[a]<order[b];
}
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];

    long timer=0;
    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;
        order[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;
        timer++;
        visited[current]=1;
        order[current]=timer;

        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);
        }
    }
    sort(leaves.begin(),leaves.end(),sorter);

    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];
        if (a==b){
        first_val[leaves[i-1]] = parent[leaves[i-1]];
        second_val[leaves[i-1]] = leaves[i-1];
        continue;
        }
        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_low=b; b= parent[b];
        }
        first_val[leaves[i-1]] = b;
        second_val[leaves[i-1]] = b_low;
    }
    for (long i = 1;i<=N;i++){
        //cout<<i<<" "<<first_val[i]<<" "<<second_val[i]<<endl;
        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() first_val = 0;second_val = 0;for (long j = 0;j<=9;j++) first_val|=(long) getHint(j+1)<<j;  for (long j = 0;j<=9;j++) second_val|=(long)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);
    //cout<<go_up<<endl;
    long j = first_val;
    if (!go_up)  j = 0;
    while (!go_up){
        j++;
        go_up  = goTo(j);
    }
    getData();
    getData();
    //cout<<j<<endl;

    while(first_val!=0){
        goTo(first_val);
        getData();
    }
    }
    long current_node=1;
    stack<long> path;
    path.push(1);
    while(goTo(second_val)){
        current_node = second_val;
        path.push(current_node);
        getData();
    }
    long endpoint = current_node;
    //cout<<"curr:"<<current_node<<endl;
    long lca = first_val;
    long next_go = second_val;

    while(path.top()!=lca){
        path.pop();
        goTo(path.top());
    }
    goTo(next_go);
    path.push(next_go);
    getData();
    while(goTo(second_val)){
        current_node = second_val;
        path.push(current_node);
        getData();
    }
    lca = first_val;
    next_go = second_val;

    while(path.top()!=endpoint){

    while(path.top()!=lca){
        path.pop();
        goTo(path.top());
    }
    goTo(next_go);
    path.push(next_go);
    getData();
    while(goTo(second_val)){
        current_node = second_val;
        path.push(current_node);
        getData();
    }
    lca = first_val;
    next_go = second_val;

    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 1128 KB Output is correct
2 Correct 100 ms 2408 KB Output is correct
3 Correct 111 ms 1352 KB Output is correct
4 Correct 131 ms 1640 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 1336 KB Output is correct
2 Correct 119 ms 1444 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1764 KB Output is correct
2 Correct 105 ms 1268 KB Output is correct
3 Correct 88 ms 1768 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 1636 KB Output is correct
2 Correct 95 ms 1280 KB Output is correct
3 Correct 96 ms 1696 KB Output is correct
4 Correct 83 ms 1624 KB Output is correct
5 Correct 92 ms 1372 KB Output is correct
6 Correct 96 ms 1688 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1368 KB Output is correct
2 Correct 90 ms 1384 KB Output is correct
3 Correct 104 ms 1196 KB Output is correct
4 Correct 97 ms 1388 KB Output is correct
5 Correct 96 ms 1680 KB Output is correct
6 Correct 104 ms 1376 KB Output is correct
7 Correct 130 ms 1708 KB Output is correct