oj.uz

Submission #1066829

# Submission time Handle Problem Language Result Execution time Memory
1066829 2024-08-20T07:49:42 Z 정희우(#11124) Speedrun (RMI21_speedrun) C++17
100 / 100
 193 ms 1700 KB 
#include "speedrun.h"
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=1010;

int n;
vint edge[MAX_N];
int check[MAX_N];
int cnt=0;

void pushbit(int v,int u,int b)
{
    //cout << v << ' ' << u << ' ' << b << '\n';
    for(int i=0;i<10;i++)
        setHint(v,i+b,u>>i&1);
}

int getbit(int b)
{
    int u=0;
    for(int i=0;i<10;i++)
        u+=getHint(i+b)<<i;
    return u;
}

void dfs(int v,int p,int u)
{
    pushbit(v,p,11);
    int non=1;
    for(auto v0 : edge[v])
        if(v0!=p)
        {
            pushbit(v,v0,1);
            non=0;
            dfs(v0,v,u);
            u=v0;
        }
    if(non)
        pushbit(v,u,1);
}

void assignHints(int subtask, int N, int A[], int B[])
{
    setHintLen(20);
    n=N;
    for(int i=1;i<n;i++)
    {
        int u=A[i],v=B[i];
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int root=1;
    for(int i=1;i<=n;i++)
        if(edge[i].size()>edge[root].size())root=i;
    dfs(root,0,edge[root].back());
}

void follow(int v,int u)
{
    //cout << v << '\n';
    if(!check[v])
    {
        check[v]=1;
        cnt++;
        if(cnt==n)return;
    }
    if(u==0)
    {
        int v0=getbit(1);
        if(goTo(v0))
            follow(v0,0);
        else
        {
            u=v0;
            int p=getbit(11);
            goTo(p);
            follow(p,u);
        }
    }
    else if(goTo(u))
        follow(u,0);
    else
    {
        int p=getbit(11);
        goTo(p);
        follow(p,u);
    }
}

void speedrun(int subtask, int N, int start)
{
    n=N;
    fill(check,check+n+1,0);
    cnt=0;
    follow(start,0);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 1196 KB Output is correct
2 Correct 149 ms 1200 KB Output is correct
3 Correct 133 ms 1700 KB Output is correct
4 Correct 167 ms 1132 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 684 KB Output is correct
2 Correct 170 ms 752 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1656 KB Output is correct
2 Correct 101 ms 940 KB Output is correct
3 Correct 113 ms 1300 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1132 KB Output is correct
2 Correct 148 ms 684 KB Output is correct
3 Correct 158 ms 684 KB Output is correct
4 Correct 157 ms 1376 KB Output is correct
5 Correct 141 ms 988 KB Output is correct
6 Correct 193 ms 944 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 1136 KB Output is correct
2 Correct 120 ms 684 KB Output is correct
3 Correct 166 ms 684 KB Output is correct
4 Correct 141 ms 1116 KB Output is correct
5 Correct 159 ms 700 KB Output is correct
6 Correct 133 ms 952 KB Output is correct
7 Correct 174 ms 688 KB Output is correct