Submission #498831

#	Time	Username	Problem	Language	Result	Execution time	Memory
498831		SlavicG	Speedrun (RMI21_speedrun)	C++17	90 / 100	138 ms	912 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ll long long
#define sz(a) (int)a.size()
#define all(v) v.begin(),v.end()

/*
void setHintLen(int l){}
void setHint(int i,int j,bool b){}
int getLength(){}
bool getHint(int j){}
bool goTo(int x){}
*/

void dfsHint(int u, int par, vector<vector<int>>& adj, vector<int>& right_neighbor, vector<int>& parent, vector<int>& left_child){
    parent[u] = par;
    vector<int> nodes;
    for(int v: adj[u]){
        if(v == par)continue;
        dfsHint(v, u, adj, right_neighbor, parent, left_child);
        nodes.pb(v);
    }
    if(sz(nodes))left_child[u] = nodes[0];
    for(int i = 0;i + 1 < sz(nodes); ++i){
        right_neighbor[nodes[i]] = nodes[i + 1];
    }
}

void assignHints(int subtask, int N, int A[], int B[]) {

    if(subtask == 1){
        setHintLen(N);
        for(int i = 1;i <= N - 1; ++i){
            setHint(A[i], B[i], 1);
            setHint(B[i], A[i], 1);
        }
    }else if(subtask == 3){
        setHintLen(20);
        vector<vector<int>> adj(N + 1);
        for(int i = 1;i <= N - 1; ++i){
            adj[A[i]].pb(B[i]);
            adj[B[i]].pb(A[i]);
        }

        for(int i = 1;i <= N; ++i){
            if(sz(adj[i]) == 1)adj[i].pb(0);
            int f = 0;
            for(int v: adj[i])
            {
                for(int j = 9;j >= 0; --j){
                    if(v & (1 << j))setHint(i, f * 10 + j + 1, 1);
                }
                ++f;
            }
        }
    }else if(subtask == 2){
        setHintLen(10);
        vector<int> deg(N + 5, 0);
        for(int i = 1;i <= N - 1; ++i){
            deg[A[i]]++;
            deg[B[i]]++;
        }
        int r = -1;
        for(int i = 1;i <= N; ++i){
            if(deg[i] == N - 1)r = i;
        }
        assert(r != -1);

        for(int i = 1;i <= N; ++i){
            for(int j = 10; j >= 1; --j){
                if(r & (1 << (j - 1)))setHint(i, j, 1);
            }
        }
    }else{
        int n = N;
        setHintLen(30);
        vector<vector<int>> adj(n + 1);
        for(int i = 1;i <= n - 1; ++i){
            adj[A[i]].pb(B[i]);
            adj[B[i]].pb(A[i]);
        }  
        vector<int> right_neighbor(n + 1, 0), parent(n + 1, 0), left_child(n + 1, 0);
        dfsHint(1, 0, adj, right_neighbor, parent, left_child);
     
        for(int i = 1;i <= n; ++i){
            int idx = 1;
            for(int j = 9;j >= 0; --j){
                if(parent[i] & (1 << j))setHint(i, idx, 1);
                ++idx;
            }
            for(int j = 9;j >= 0; --j){
                if(left_child[i] & (1 << j))setHint(i, idx, 1);
                ++idx;
            }
            for(int j = 9;j >= 0; --j){
                if(right_neighbor[i] & (1 << j))setHint(i, idx, 1);
                ++idx;
            }
        }
    }
}

void dfs1(int u, int par, vector<bool>& vis, int n){
    vis[u] = true;
    for(int v = 1;v <= n; ++v){
        if(!vis[v] && getHint(v) == 1){
            int x = goTo(v);
            assert(x == 1);
            dfs1(v, u, vis, n);
        }
    }
    if(par != -1){
        int x = goTo(par);
        assert(x == 1);
    }
}

void dfs3(int u, int par, vector<bool>& vis, vector<vector<int>>& adj){
    vis[u] = true;

    int A = 0, B = 0;
    for(int j = 20;j >= 11; --j){
        if(getHint(j) == 1){
            A += (1 << (j - 10 - 1));
        }
    }
    for(int j = 10; j >= 1; --j){
        if(getHint(j) == 1){
            B += (1 << (j - 1));
        }
    }
    adj[u].pb(A);
    adj[u].pb(B);

    for(int v: adj[u]){
        if(v == 0)continue;
        if(!vis[v]){
            int x = goTo(v);
            assert(x == 1);
            dfs3(v, u, vis, adj);
        }
    }

    if(par != -1){
        int x = goTo(par);
        assert(x == 1);
    }
}

void dfs4(int u, vector<bool>& vis){
    int lc = 0, rn = 0, par = 0, idx = 1;
 
    for(int j = 9;j >= 0; --j){
        if(getHint(idx))par += (1 << j);
        ++idx;
    }
    for(int j = 9;j >= 0; --j){
        if(getHint(idx))lc += (1 << j);
        ++idx;
    }
    for(int j = 9;j >= 0; --j){
        if(getHint(idx))rn += (1 << j);
        ++idx;
    }
 
    vis[u] = true;
 
    if(lc && !vis[lc]){
        goTo(lc);
        dfs4(lc, vis);
    }
 
    if(par != 0 && rn){  
        goTo(par);
        goTo(rn);
        dfs4(rn, vis);
    }
 
    if(par != 0){
        goTo(par);
        dfs4(par, vis);
    }
}
void speedrun(int subtask, int N, int start) {
    if(subtask == 1){
        int l = getLength();
        vector<bool> vis(N + 5, false);
        dfs1(start, -1, vis, N);
    }else if(subtask == 3){
        int l = getLength();
        vector<bool> vis(N + 5, false);
        vector<vector<int>> adj(N + 5);
        dfs3(start, -1, vis, adj);
    }else if(subtask == 2){
        int l = getLength();
        int r = 0;
        for(int j = 1;j <= 10; ++j){
            if(getHint(j) == 1)r += (1 << (j - 1));
        }

        if(start != r)goTo(r);

        for(int i = 1;i <= N; ++i){
            if(r != i){
                goTo(i);
                goTo(r);
            }
        }
    }else{
        int l = getLength();
        vector<bool> vis(N + 5, false);
        dfs4(start, vis);
    }
}

/*
int32_t main(){

}
*/

Compilation message (stderr)

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:190:13: warning: unused variable 'l' [-Wunused-variable]
  190 |         int l = getLength();
      |             ^
speedrun.cpp:194:13: warning: unused variable 'l' [-Wunused-variable]
  194 |         int l = getLength();
      |             ^
speedrun.cpp:199:13: warning: unused variable 'l' [-Wunused-variable]
  199 |         int l = getLength();
      |             ^
speedrun.cpp:214:13: warning: unused variable 'l' [-Wunused-variable]
  214 |         int l = getLength();
      |             ^

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 30 / 40