oj.uz

Submission #1066843

# Submission time Handle Problem Language Result Execution time Memory
1066843 2024-08-20T08:00:37 Z 정민찬(#11123) Speedrun (RMI21_speedrun) C++17
100 / 100
 148 ms 1964 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

void setHintLen(int l);
void setHint(int i, int j, bool b);
int getLength();
bool getHint(int j);
bool goTo(int x);

vector<int> adj[1010];
vector<int> g[1010];
int par[1010];

void dfs(int x, int p) {
    for (auto &y : adj[x]) {
        if (y == p) continue;
        g[x].push_back(y);
        par[y] = x;
        dfs(y, x);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) {
    for (int i=1; i<=N-1; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    par[1] = 0;
    dfs(1, 0);
    setHintLen(20);
    for (int i=1; i<=N; i++) {
        int fir = 0;
        if (!g[i].empty()) fir = g[i][0];
        for (int j=0; j<10; j++) {
            setHint(i, j+1, (bool)((1<<j) & fir));
        }
    }
    for (int i=1; i<=N; i++) {
        if (g[i].empty()) continue;
        for (int j=0; j<g[i].size()-1; j++) {
            for (int k=0; k<10; k++) {
                setHint(g[i][j], k+10+1, (bool)((1<<k) & g[i][j+1]));
            }
        }
        for (int k=0; k<10; k++) {
            setHint(g[i].back(), k+10+1, (bool)((1<<k) & par[i]));
        }
    }
}

int vis[1010];

int dfs2(int x) {
    int fir = 0;
    int nxt = 0;
    for (int i=0; i<10; i++) {
        fir ^= (getHint(i+1) << i);
        nxt ^= (getHint(i+10+1) << i);
    }
    if (vis[x]) return nxt;
    vis[x] = 1;
    if (fir == 0) return nxt;
    int y = fir;
    while (true) {
        if (y == 0 || !goTo(y)) break;
        y = dfs2(y);
        goTo(x);
    }
    return nxt;
}

void speedrun(int subtask, int N, int start) {
    if (N == 1) return;
    int fir = 0;
    for (int i=0; i<10; i++) {
        fir ^= (getHint(i+1) << i);
    }
    if (fir == 0) {
        for (int i=1; i<=N; i++) {
            if (i == start) continue;
            int ret = goTo(i);
            if (ret) {
                start = i;
                break;
            }
        }
    }
    dfs2(start);
    for (int i=1; i<=N; i++) {
        assert(vis[i]);
    }
}
/*
static map<int, map<int, bool>> mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int>> neighbours;

void setHintLen(int l) {
    if (length_set) {
        cerr << "Cannot call setHintLen twice" << endl;
        exit(0);
    }
    length = l;
    length_set = true;
}

void setHint(int i, int j, bool b) {
    if (!length_set) {
        cerr << "Must call setHintLen before setHint" << endl;
        exit(0);
    }
    mp[i][j] = b;
}

int getLength() { return length; }

bool getHint(int j) { return mp[current_node][j]; }

bool goTo(int x) {
    if (neighbours[current_node].find(x) == end(neighbours[current_node])) {
        ++queries;
        return false;
    } else {
        viz.insert(current_node = x);
        return true;
    }
}

int main() {
    int N;
    cin >> N;

    int a[N], b[N];
    for (int i = 1; i < N; ++i) {
        cin >> a[i] >> b[i];
        neighbours[a[i]].insert(b[i]);
        neighbours[b[i]].insert(a[i]);
    }

    assignHints(1, N, a, b);

    if (!length_set) {
        cerr << "Must call setHintLen at least once" << endl;
        exit(0);
    }

    cin >> current_node;
    viz.insert(current_node);

    speedrun(1, N, current_node);

    if (viz.size() < N) {
        cerr << "Haven't seen all nodes" << endl;
        exit(0);
    }

    cerr << "OK; " << queries << " incorrect goto's" << endl;
    return 0;
}
*/

Compilation message

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

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 688 KB Output is correct
2 Correct 118 ms 1964 KB Output is correct
3 Correct 112 ms 1192 KB Output is correct
4 Correct 142 ms 940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 884 KB Output is correct
2 Correct 114 ms 940 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 1212 KB Output is correct
2 Correct 126 ms 1212 KB Output is correct
3 Correct 148 ms 952 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 932 KB Output is correct
2 Correct 138 ms 1168 KB Output is correct
3 Correct 130 ms 880 KB Output is correct
4 Correct 119 ms 684 KB Output is correct
5 Correct 123 ms 1128 KB Output is correct
6 Correct 110 ms 684 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 684 KB Output is correct
2 Correct 117 ms 684 KB Output is correct
3 Correct 121 ms 688 KB Output is correct
4 Correct 122 ms 1188 KB Output is correct
5 Correct 123 ms 960 KB Output is correct
6 Correct 118 ms 1140 KB Output is correct
7 Correct 123 ms 684 KB Output is correct