oj.uz

Submission #859165

# Submission time Handle Problem Language Result Execution time Memory
859165 2023-10-09T21:14:21 Z Vanio Speedrun (RMI21_speedrun) C++17
100 / 100
 115 ms 2576 KB 
#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;

int n,f[1001],pr,f2[1001];
vector<int> v[1001];

void encode(int p, int k, int indx){
    int i=indx;
    while(k>0){
        setHint(p,i,k%2);
        k/=2;
        i++;
    }
}

void dfsen(int k, int par){
    if(f[pr]==2){
        encode(pr,k,1);
        encode(pr,par,11);
    }
    if(v[k].size()==1 && k!=1){f[k]=2; pr=k; return;}
    f[k]=1;
    pr=k;
    encode(k,par,1);
    for(int i=0;i<v[k].size();i++){
        if(f[v[k][i]]==0){
            if(f2[k]==0){
                encode(k,v[k][i],11);
                f2[k]=1;
            }
            dfsen(v[k][i],k);
        }
    }
}

void assignHints(int subtask, int N, int a[], int b[]){
    n=N;
    int i;
    for(i=1;i<n;i++){
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    setHintLen(20);
    dfsen(1,0);
}



int decode(int indx){
    int s=0,t=512,i;
    for(i=indx;i>indx-10;i--){
        s+=getHint(i)*t;
        t/=2;
    }
    return s;
}

void dfssr(int k,int par){
    if(par!=decode(10)){
        v[decode(20)].push_back(decode(10));
        goTo(par);
        return;
    }
    v[k].push_back(decode(20));
    for(int i=0;i<v[k].size();i++){
        goTo(v[k][i]);
        dfssr(v[k][i],k);
    }
    if(par==0) return;
    goTo(par);
}

void speedrun(int subtask, int N, int start){
    n=N;
    int i,t1,t2;
    t1=decode(10);
    t2=decode(20);
    if(t1==0 && t2==0){
        for(i=1;i<=n;i++){
            if(i==start) continue;
            if(goTo(i)) break;
        }
    }
    else if(t1!=0){
        if(!goTo(t1)){
            for(i=1;i<=n;i++){
                if(i==start || i==t1) continue;
                if(goTo(i)) break;
            }
        }
    }
    while(t1=decode(10)) goTo(t1);
    dfssr(1,0);
}

Compilation message

speedrun.cpp: In function 'void dfsen(int, int)':
speedrun.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<v[k].size();i++){
      |                 ~^~~~~~~~~~~~
speedrun.cpp: In function 'void dfssr(int, int)':
speedrun.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=0;i<v[k].size();i++){
      |                 ~^~~~~~~~~~~~
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:93:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   93 |     while(t1=decode(10)) goTo(t1);
      |           ~~^~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1564 KB Output is correct
2 Correct 100 ms 2068 KB Output is correct
3 Correct 88 ms 1404 KB Output is correct
4 Correct 92 ms 1684 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 1392 KB Output is correct
2 Correct 92 ms 1152 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 1672 KB Output is correct
2 Correct 109 ms 2376 KB Output is correct
3 Correct 81 ms 2164 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1408 KB Output is correct
2 Correct 92 ms 1396 KB Output is correct
3 Correct 94 ms 1652 KB Output is correct
4 Correct 100 ms 2576 KB Output is correct
5 Correct 109 ms 1396 KB Output is correct
6 Correct 96 ms 1652 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1652 KB Output is correct
2 Correct 107 ms 1392 KB Output is correct
3 Correct 88 ms 1296 KB Output is correct
4 Correct 95 ms 2160 KB Output is correct
5 Correct 73 ms 1664 KB Output is correct
6 Correct 89 ms 1668 KB Output is correct
7 Correct 103 ms 884 KB Output is correct