oj.uz

Submission #1091990

# Submission time Handle Problem Language Result Execution time Memory
1091990 2024-09-22T19:03:27 Z alexdd Speedrun (RMI21_speedrun) C++17
100 / 100
 72 ms 1380 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> con[1005];
int parent[1005];
void pune_hint(int nod, int x, int y)
{
    //cerr<<nod<<"  "<<x<<" & "<<y<<" hint\n";
    for(int i=0;i<10;i++)
    {
        if(((1<<i)&x))
            setHint(nod,i+1,1);
        if(((1<<i)&y))
            setHint(nod,i+11,1);
    }
}
void dfs(int nod, int par, int tori)
{
    parent[nod]=par;
    vector<int> v;
    for(int adj:con[nod])
        if(adj!=par)
            v.push_back(adj);
    for(int i=0;i<v.size();i++)
    {
        if(i+1 < v.size())
            dfs(v[i],nod,v[i+1]);
        else
            dfs(v[i],nod,0);
    }
    if(tori==0)
    {
        if(v.empty()) pune_hint(nod,parent[par],0);
        else pune_hint(nod,parent[par],v[0]);
    }
    else
    {
        if(v.empty()) pune_hint(nod,tori,0);
        else pune_hint(nod,tori,v[0]);
    }
}
void assignHints(int subtask, int N, int A[], int B[])
{
    setHintLen(20);
    for(int i=1;i<N;i++)
    {
        con[A[i]].push_back(B[i]);
        con[B[i]].push_back(A[i]);
    }
    dfs(1,0,0);
}
int get1()
{
    int aux=0;
    for(int i=0;i<10;i++)
        if(getHint(i+1))
            aux += (1<<i);
    return aux;
}
int get2()
{
    int aux=0;
    for(int i=0;i<10;i++)
        if(getHint(i+11))
            aux += (1<<i);
    return aux;
}
int nxt[1005],down[1005];
void dfs_speedrun(int nod, int par)
{
    //cerr<<nod<<" "<<par<<" dfs\n";
    nxt[nod] = get1();
    down[nod] = get2();
    if(down[nod]==0)///e frunza
    {
        if(par!=0) assert(goTo(par));
        return;
    }
    int c = down[nod];
    while(1)
    {
        assert(goTo(c));
        dfs_speedrun(c,nod);
        c = nxt[c];
        if(c==par)
            break;
    }
    if(par!=0) assert(goTo(par));
}
void speedrun(int subtask, int N, int start)
{
    if(N==1)
        return;
    int cur=start;
    while(1)
    {
        down[cur] = get2();
        if(down[cur]==0)
            break;
        assert(goTo(down[cur]));
        cur = down[cur];
    }
    int p=-1;
    for(int i=1;i<=N;i++)
    {
        if(i!=cur && goTo(i))
        {
            p=i;
            break;
        }
    }
    assert(p!=-1);
    ///suntem in p
    assert(goTo(cur));
    while(cur!=1)
    {
        //cerr<<cur<<" "<<p<<" zzz\n";
        nxt[cur] = get1();
        //cerr<<cur<<" "<<nxt[cur]<<" nxt\n";
        assert(goTo(p));
        if(p==1)
        {
            cur=1;
            break;
        }
        if(nxt[cur]==0 || !goTo(nxt[cur]))
        {
            swap(cur,p);
        }
        else
        {
            cur = nxt[cur];
        }
        //assert(goTo(nxt[cur]));
    }
    if(cur!=1) while(1);
    assert(cur==1);
    dfs_speedrun(1,0);
}
/**
5
1 2
2 3
3 4
3 5
4
*/

Compilation message

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

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 888 KB Output is correct
2 Correct 48 ms 1372 KB Output is correct
3 Correct 69 ms 1096 KB Output is correct
4 Correct 50 ms 856 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 684 KB Output is correct
2 Correct 32 ms 944 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 956 KB Output is correct
2 Correct 71 ms 1200 KB Output is correct
3 Correct 62 ms 1188 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 688 KB Output is correct
2 Correct 57 ms 1240 KB Output is correct
3 Correct 48 ms 920 KB Output is correct
4 Correct 50 ms 944 KB Output is correct
5 Correct 51 ms 932 KB Output is correct
6 Correct 44 ms 744 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 684 KB Output is correct
2 Correct 47 ms 684 KB Output is correct
3 Correct 34 ms 684 KB Output is correct
4 Correct 39 ms 1360 KB Output is correct
5 Correct 40 ms 684 KB Output is correct
6 Correct 52 ms 1380 KB Output is correct
7 Correct 28 ms 684 KB Output is correct