oj.uz

Submission #593461

# Submission time Handle Problem Language Result Execution time Memory
593461 2022-07-11T08:30:25 Z pakhomovee Speedrun (RMI21_speedrun) C++17
100 / 100
 234 ms 928 KB 
#include "speedrun.h"
#include <vector>
#include <iostream>
#include <set>

using namespace std;

vector<pair<int, int>> gg;
vector<int> ord;
vector<int> ids;
int id = 0;

void dfs(int v, vector<vector<int>> &g, int p) {
    gg[v].first = p;
    ord.push_back(v);
    ids[v] = id++;
    for (int u : g[v]) {
        if (u != p) {
            dfs(u, g, v);
        }
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    vector<vector<int>> g(N);
    for (int i = 1; i < N; ++i) {
        int u = A[i], v = B[i];
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    gg.resize(N);
    ids.resize(N);
    dfs(0, g, 0);
    for (int i = 0; i < N; ++i) {
        gg[i].second = ord[(ids[i] + 1) % N];
    }
    for (int i = 0; i < N; ++i) {
        int val = gg[i].first * (1 << 10) + gg[i].second;
        //cout << i << ' ' << gg[i].second << endl;
        for (int j = 0; j < 20; ++j) {
            if ((1 << j) & val) {
                setHint(i + 1, j + 1, 1);
            } else {
                setHint(i + 1, j + 1, 0);
            }
        }
    }
    cout << endl;
}

set<int> vis;
int n;

void work(int v, int nx) {
    vis.insert(v);
    int nxt = 0;
    int par = 0;
    for (int j = 0; j < 10; ++j) {
        nxt += (1 << j) * getHint(j + 1);
    }
    for (int j = 10; j < 20; ++j) {
        par += (1 << (j - 10)) * getHint(j + 1);
    }
    if (nx == -1) {
        nx = nxt;
    }
    if (vis.size() == n) {
        return;
    }
    //cout << v << ' ' << par << ' ' << nxt << endl;
    if (goTo(nx + 1)) {
        work(nx, -1);
    } else {
        goTo(par + 1);
        work(par, nx);
    }
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    n = N;
    work(start - 1, -1);
}

Compilation message

speedrun.cpp: In function 'void work(int, int)':
speedrun.cpp:69:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     if (vis.size() == n) {
      |         ~~~~~~~~~~~^~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 848 KB Output is correct
2 Correct 188 ms 792 KB Output is correct
3 Correct 196 ms 840 KB Output is correct
4 Correct 107 ms 832 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 872 KB Output is correct
2 Correct 175 ms 792 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 928 KB Output is correct
2 Correct 179 ms 796 KB Output is correct
3 Correct 162 ms 844 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 740 KB Output is correct
2 Correct 208 ms 792 KB Output is correct
3 Correct 234 ms 800 KB Output is correct
4 Correct 171 ms 852 KB Output is correct
5 Correct 190 ms 824 KB Output is correct
6 Correct 114 ms 804 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 792 KB Output is correct
2 Correct 191 ms 792 KB Output is correct
3 Correct 187 ms 808 KB Output is correct
4 Correct 180 ms 848 KB Output is correct
5 Correct 199 ms 840 KB Output is correct
6 Correct 165 ms 836 KB Output is correct
7 Correct 218 ms 752 KB Output is correct