oj.uz

Submission #1097380

# Submission time Handle Problem Language Result Execution time Memory
1097380 2024-10-07T06:08:38 Z heeheeheehaaw Speedrun (RMI21_speedrun) C++17
100 / 100
 139 ms 1132 KB 
#include <bits/stdc++.h>
#include "speedrun.h"

using namespace std;

vector<int> adj[1005];
bool visited[1005];
vector<int> ord;
int parent[1005];
int vis[1005];

void dfs(int nod, int par)
{
    parent[nod] = par;
    if(!visited[nod])
        visited[nod] = true, ord.push_back(nod);
    for(auto it : adj[nod])
    {
        if(it != par)
            dfs(it, nod);
    }
}

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

    dfs(1, 1);

    for(int i = 0; i < ord.size() - 1; i++)
    {
        for(int b = 0; b < 10; b++)
        {
            if(((1 << b) & (ord[i + 1])) != 0)
                setHint(ord[i], b + 1, 1);
            else
                setHint(ord[i], b + 1, 0);
        }
    }

    for(int i = 0; i < ord.size(); i++)
    {
        for(int b = 0; b < 10; b++)
        {
            if(((1 << b) & parent[ord[i]]) != 0)
                setHint(ord[i], b + 1 + 10, 1);
            else
                setHint(ord[i], b + 1 + 10, 0);
        }
    }

    for(int b = 0; b < 10; b++)
    {
        if(((1 << b) & (ord[0])) != 0)
            setHint(ord.back(), b + 1, 1);
        else
            setHint(ord.back(), b + 1, 0);
    }
}

void speedrun(int subtask, int n, int start)
{
    int curr = start, cnt = n, nxt = -1;
    while(cnt > 0)
    {
        if(vis[curr] == 0)
            cnt--, vis[curr] = 1;
        int u = 0, par = 0;
        for(int i = 1; i <= 10; i++)
            u += (1 << (i - 1)) * getHint(i);
        if(nxt != -1)
            u = nxt;
        for(int i = 11; i <= 20; i++)
            par += (1 << (i - 1 - 10)) * getHint(i);
        bool ok = goTo(u);
        if(ok == true)
        {
            curr = u;
            nxt = -1;
        }
        else
        {
            goTo(par);
            curr = par;
            nxt = u;
        }
    }

    return;
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0; i < ord.size() - 1; i++)
      |                    ~~^~~~~~~~~~~~~~~~
speedrun.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < ord.size(); i++)
      |                    ~~^~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 740 KB Output is correct
2 Correct 120 ms 892 KB Output is correct
3 Correct 113 ms 688 KB Output is correct
4 Correct 138 ms 940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1116 KB Output is correct
2 Correct 127 ms 948 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 716 KB Output is correct
2 Correct 108 ms 684 KB Output is correct
3 Correct 122 ms 684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 944 KB Output is correct
2 Correct 121 ms 940 KB Output is correct
3 Correct 129 ms 868 KB Output is correct
4 Correct 118 ms 856 KB Output is correct
5 Correct 115 ms 932 KB Output is correct
6 Correct 104 ms 688 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 1120 KB Output is correct
2 Correct 124 ms 1132 KB Output is correct
3 Correct 93 ms 684 KB Output is correct
4 Correct 110 ms 940 KB Output is correct
5 Correct 123 ms 936 KB Output is correct
6 Correct 119 ms 940 KB Output is correct
7 Correct 111 ms 932 KB Output is correct