oj.uz

Submission #503403

# Submission time Handle Problem Language Result Execution time Memory
503403 2022-01-07T20:24:25 Z Stickfish Speedrun (RMI21_speedrun) C++17
100 / 100
 126 ms 916 KB 
#include "speedrun.h"
#include <vector>
#include <cassert>
#include <bitset>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 1000;
const int LEN = 10;
const int MEM = 20;
vector<int> edg[MAXN];
int root[MAXN];

void dfs_init(int v) {
    for (int i = 0; i < edg[v].size(); ++i) {
        if (edg[v][i] == root[v]) {
            edg[v].erase(edg[v].begin() + i);
            break;
        }
    }
    for (auto u : edg[v]) {
        if (u == root[v])
            continue;
        root[u] = v;
        dfs_init(u);
    }
}

void write(int v, int x, int ps) {
    for (int i = 0; i < LEN; ++i) {
        if (x & (1 << i)) {
            //cout << i + 1 + ps * LEN << endl;
            setHint(v + 1, i + 1 + ps * LEN, 1);
        }
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    for (int i = 1; i < N; ++i) {
        --A[i];
        --B[i];
        edg[A[i]].push_back(B[i]);
        edg[B[i]].push_back(A[i]);
        //cout << A[i] << ' ' << B[i] << endl;
    }
    setHintLen(20);
    dfs_init(0);
    for (int i = 0; i < N; ++i) {
        if (edg[i].size()) {
            write(i, edg[i][0], 0);
            write(edg[i].back(), root[i], 1);
        } else {
            write(i, root[i], 0);
        }
        int s = edg[i].size();
        for (int j = 0; j + 1 < s; ++j) {
            write(edg[i][j], edg[i][(j + 1) % s], 1);
        }
    }
}

bitset<MEM> bs[MAXN];
bitset<MAXN> used;

int read(int v, int ps) {
    if (!used[v]) {
        used[v] = 1;
        for (int i = 0; i < MEM; ++i) {
            bs[v][i] = getHint(i + 1);
        }
    }
    if (ps == 0) {
        return ((bs[v] << LEN) >> LEN).to_ullong();
    } else {
        return (bs[v] >> LEN).to_ullong();
    }
}

void dfs_ans(int v) {
    //cerr << v << endl;
    int u0 = read(v, 0);
    //if (u0 == v) {
        //assert(0);
    //}
    int u = u0;
    int cnt = 0;
    do {
        if (!used[u]) {
            //cout << v << " -> " << u << endl;
            if (!goTo(u + 1)) {
                return;
            }
            dfs_ans(u);
            assert(goTo(v + 1));
        } else {
            //cout << v << " => " << u << endl;
        }
        assert(used[u]);
        if (u == 0)
            return;
        u = read(u, 1);
    } while (u != u0);
}

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

Compilation message

speedrun.cpp: In function 'void dfs_init(int)':
speedrun.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < edg[v].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
speedrun.cpp: In function 'void dfs_ans(int)':
speedrun.cpp:87:9: warning: unused variable 'cnt' [-Wunused-variable]
   87 |     int cnt = 0;
      |         ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 668 KB Output is correct
2 Correct 88 ms 660 KB Output is correct
3 Correct 95 ms 712 KB Output is correct
4 Correct 84 ms 668 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 700 KB Output is correct
2 Correct 51 ms 820 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 776 KB Output is correct
2 Correct 90 ms 676 KB Output is correct
3 Correct 115 ms 720 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 740 KB Output is correct
2 Correct 105 ms 676 KB Output is correct
3 Correct 90 ms 660 KB Output is correct
4 Correct 86 ms 668 KB Output is correct
5 Correct 114 ms 720 KB Output is correct
6 Correct 101 ms 660 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 676 KB Output is correct
2 Correct 105 ms 688 KB Output is correct
3 Correct 78 ms 916 KB Output is correct
4 Correct 126 ms 660 KB Output is correct
5 Correct 102 ms 676 KB Output is correct
6 Correct 110 ms 712 KB Output is correct
7 Correct 97 ms 708 KB Output is correct