oj.uz

Submission #641447

# Submission time Handle Problem Language Result Execution time Memory
641447 2022-09-16T18:27:26 Z Summers Speedrun (RMI21_speedrun) C++14
100 / 100
 238 ms 996 KB 
#include "speedrun.h"
#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<long long>v[2000], s;
long long n, fath[1005];

void dfs(long long vr,long long f)
{
    s.push_back(vr);
    fath[vr]=f;

    for(int i=0;i<v[vr].size();i++)
    {
        if(v[vr][i]!=f)dfs(v[vr][i],vr);
    }

}

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

    long long i,j;

    setHintLen(20);

    n=N;
    for(i=1;i<N;i++)
    {
            v[A[i]].push_back(B[i]);
            v[B[i]].push_back(A[i]);
    }
    dfs(1,-1);


    for(i=0;i<n;i++)
    {
        long long f = fath[s[i]];
        long long node = s[(i+1)%n];

        for(j=1;j<=10;j++)
        {
            setHint(s[i],j,((1<<(j-1))&f));
            setHint(s[i],j+10,((1<<(j-1))&node));
        }
    }

}

void speedrun(int subtask, int N, int start) {

    int i,j;
    for(i=1;i<=N;i++)
    {
        long long node=0;
            for(j=11;j<=20;j++)
            {
                node=node|((getHint(j))<<(j-11));
            }
        while(!goTo(node))
        {
            long long f=0;
            for(j=1;j<=10;j++)
            {
                f=f|((getHint(j))<<(j-1));
            }
            goTo(f);
        }
    }

}

Compilation message

speedrun.cpp: In function 'void dfs(long long int, long long int)':
speedrun.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<v[vr].size();i++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 816 KB Output is correct
2 Correct 207 ms 868 KB Output is correct
3 Correct 237 ms 672 KB Output is correct
4 Correct 154 ms 672 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 956 KB Output is correct
2 Correct 218 ms 944 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 800 KB Output is correct
2 Correct 157 ms 996 KB Output is correct
3 Correct 211 ms 800 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 672 KB Output is correct
2 Correct 218 ms 672 KB Output is correct
3 Correct 189 ms 876 KB Output is correct
4 Correct 238 ms 872 KB Output is correct
5 Correct 91 ms 732 KB Output is correct
6 Correct 235 ms 828 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 672 KB Output is correct
2 Correct 178 ms 748 KB Output is correct
3 Correct 192 ms 780 KB Output is correct
4 Correct 141 ms 848 KB Output is correct
5 Correct 197 ms 852 KB Output is correct
6 Correct 187 ms 732 KB Output is correct
7 Correct 115 ms 864 KB Output is correct