Submission #499143

#	Time	Username	Problem	Language	Result	Execution time	Memory
499143		wdjpng	Speedrun (RMI21_speedrun)	C++17	100 / 100	317 ms	916 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i<n;i++)
#define all(a) a.begin(), a.end()

using namespace std;

void sett(int v, int a, int b)
{
    if(b==-1) b=1023;
    rep(i, 10) setHint(v, i+1, 0);
    rep(i, 10) setHint(v, i+11,0);
    rep(i, 10) if((a>>i)&1) setHint(v, i+1, 1);
    rep(i, 10) if((b>>i)&1) setHint(v, i+11, 1);
}

int dfs(int v, int p, vector<vector<int>>&E)
{
    int last_leave = -1;

    for(int w : E[v]) 
    {
        if(w==p) continue;
        int c_leave = dfs(w,v,E);
        if(last_leave==-1)
        {
            sett(v, w, p); // just go down and encode parent
        } else {
            sett(last_leave, v, w);
        }
        last_leave = c_leave;
    }

    if(last_leave == -1) last_leave=v;
    if(p==-1) sett(last_leave, 1023, 1023);
    return last_leave;
}

void assignHints(signed subtask, signed N, signed A[], signed B[]) {  
    setHintLen(20);

    int n = N;
    if(n==1)return;
    vector<vector<int>>E(n+1);
    for(int i = 1; i < n; i++) 
    {
        E[A[i]].push_back(B[i]);
        E[B[i]].push_back(A[i]);
    }

    dfs(1, -1, E);
    return;
}

pair<int, int>read()
{
    pair<int, int>p = make_pair(0,0);
    for(int i = 0; i < 10; i++)
    {
        if(getHint(i+1))  p.first+=1<<i;
        if(getHint(i+11)) p.second+=1<<i;
    }
    return p;
}
int sec(stack<int>& s)
{
    assert(s.size()>1);
    int tmp = s.top(); 
    s.pop();
    int tmp2 = s.top();
    s.push(tmp);
    return tmp2;
}
void start_from_root(int n)
{
    int v = 1;
    stack<int>s;
    s.push(1);
    
    while (read().first!=1023)
    {
        if(read().second!=1023&&read().second!=sec(s))
        {
            pair<int, int>c_read= read();
            while (v!=c_read.first) // go to parent with unvisited child
            {
                s.pop();
                goTo(s.top());
                v=s.top();
            }
            goTo(c_read.second); //goto child
            s.push(c_read.second);
            v=c_read.second;
        } else 
        {
            // go to child (since the current node is not a leaf)
            v=read().first;
            goTo(v);
            s.push(v);
        }
    }
    
    return;
}
void speedrun(signed subtask, signed N, signed start) { /* your solution here */
    int n=N;
    if(n==1) return;
    if(start==1) return start_from_root(n);

    vector<int>neigh;
    for(int i = 1; i <=n; i++)
    {
        if(i==start) continue;
        if(goTo(i))
        {
            goTo(start);
            neigh.push_back(i);
        }
        if(neigh.size()>1) break;
    }

    if(neigh.size()==1) {goTo(neigh[0]);} //leave, go to parent
  
    while (read().second!=1023)
    {
        goTo(read().second);
    }
    start_from_root(n);
}

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