oj.uz

답안 #1104347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104347 2024-10-23T13:38:34 Z M_W_13 Speedrun (RMI21_speedrun) C++17
100 / 100
 193 ms 1660 KB 
#include <bits/stdc++.h>
#include "speedrun.h"

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)

const int MAXN = 1001;
vector<int> graf[MAXN];
vector<int> kolejnosc;

void dfset(int v, int last) {
    kolejnosc.push_back(v);
    int x = 1;
    for (int j = 11; j <= 20; j++) {
        if ((x & last) == x) {
            setHint(v, j, 1);
        }
        else {
            setHint(v, j, 0);
        }
        x *= 2;
    }
    for (auto syn: graf[v]) {
        if (syn == last) {
            continue;
        }
        dfset(syn, v);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    for (int i = 1; i < N; i++) {
        // cout << "i = " << i << endl;
        // cout << A[i] << " " << B[i] << endl;
        graf[A[i]].push_back(B[i]);
        graf[B[i]].push_back(A[i]);
    }
    // cout << "TU1" << endl;
    dfset(1, 1);
    // cout << "TU2" << endl;
    rep(i, N) {
        int v = kolejnosc[i];
        int w = kolejnosc[(i + 1) % N];
        int x = 1;
        for (int j = 1; j <= 10; j++) {
            if ((x & w) == x) {
                setHint(v, j, 1);
            }
            else {
                setHint(v, j, 0);
            }
            x *= 2;
        }
    }
}
const int MAXN2 = 1001;
bool czy[MAXN2];

int dfs(int v, int last) {
    czy[v] = true;
    // cout << "v = " << v << endl;
    int nowy = 0;
    int x = 1;
    for (int j = 1; j <= 10; j++) {
        if (getHint(j)) {
            nowy += x;
        }
        x *= 2;
    }
    // cout << "nowy = " << nowy << '\n';
    if (czy[nowy]) {
        goTo(last);
        return nowy;
    }
    while (!czy[nowy] && goTo(nowy)) {
        nowy = dfs(nowy, v);
    }
    goTo(last);
    return nowy;
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    getLength();
    int v = start;
    while (v != 1) { 
        int nekst = 0;
        int x = 1;
        for (int j = 11; j <= 20; j++) {
            if (getHint(j)) {
                nekst += x;
            }
            x *= 2;
        }
        // cout << "nekst = " << nekst << endl;
        goTo(nekst);
        v = nekst;
    }
    dfs(1, 1);
}

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 1056 KB Output is correct
2 Correct 183 ms 1148 KB Output is correct
3 Correct 193 ms 1312 KB Output is correct
4 Correct 164 ms 1100 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 1120 KB Output is correct
2 Correct 170 ms 1056 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 1428 KB Output is correct
2 Correct 165 ms 1388 KB Output is correct
3 Correct 166 ms 1660 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 884 KB Output is correct
2 Correct 159 ms 1424 KB Output is correct
3 Correct 160 ms 1348 KB Output is correct
4 Correct 159 ms 1652 KB Output is correct
5 Correct 181 ms 916 KB Output is correct
6 Correct 175 ms 1068 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 1308 KB Output is correct
2 Correct 173 ms 1092 KB Output is correct
3 Correct 184 ms 840 KB Output is correct
4 Correct 170 ms 1596 KB Output is correct
5 Correct 186 ms 944 KB Output is correct
6 Correct 177 ms 1084 KB Output is correct
7 Correct 174 ms 1060 KB Output is correct