Submission #923326

#	Time	Username	Problem	Language	Result	Execution time	Memory
923326		MinhAnhnd	Speedrun (RMI21_speedrun)	C++14	100 / 100	131 ms	2408 KiB

speedrun

#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 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40