oj.uz

Submission #499143

# Submission time Handle Problem Language Result Execution time Memory
499143 2021-12-27T09:57:06 Z wdjpng Speedrun (RMI21_speedrun) C++17
100 / 100
 317 ms 916 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 668 KB Output is correct
2 Correct 283 ms 672 KB Output is correct
3 Correct 221 ms 736 KB Output is correct
4 Correct 282 ms 728 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 668 KB Output is correct
2 Correct 256 ms 660 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 684 KB Output is correct
2 Correct 242 ms 756 KB Output is correct
3 Correct 278 ms 688 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 676 KB Output is correct
2 Correct 240 ms 916 KB Output is correct
3 Correct 276 ms 696 KB Output is correct
4 Correct 242 ms 688 KB Output is correct
5 Correct 256 ms 676 KB Output is correct
6 Correct 211 ms 668 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 660 KB Output is correct
2 Correct 291 ms 672 KB Output is correct
3 Correct 317 ms 684 KB Output is correct
4 Correct 280 ms 752 KB Output is correct
5 Correct 267 ms 684 KB Output is correct
6 Correct 257 ms 660 KB Output is correct
7 Correct 307 ms 832 KB Output is correct