oj.uz

Submission #504898

# Submission time Handle Problem Language Result Execution time Memory
504898 2022-01-10T09:50:13 Z daongocha Speedrun (RMI21_speedrun) C++14
19 / 100
 217 ms 736 KB 
#include <bits/stdc++.h>
 
#include "speedrun.h"
 
#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
 
using namespace std;
 
const int MAXN = 1005;
vector<int> path[MAXN];
vector<int> order;
int parent[MAXN];
 
// void assignHints(int subtask, int N, int A[], int B[]);
// void speedrun(int subtask, int N, int start);
 
// void setHintLen(int l);
// void setHint(int i, int j, bool b);
// int getLength();
// bool getHint(int j);
// bool goTo(int x);
 
void dfs(int u, int pre = 0) {
  //  cout << u << endl;
    order.push_back(u);
    parent[u] = pre;
    for (int v: path[u])
        if (v != pre) dfs(v, u);
}
 
void assignHints(int sub, int n, int A[], int B[]) {
    for (int i = 1; i < n; i++) {
        int u = A[i], v = B[i];
        path[u].push_back(v);
        path[v].push_back(u);
    }
    
    dfs(1);
 
    setHintLen(20);
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i], v = (i + 1 >= n ? 0 : order[i + 1]);
        for (int j = 1; j <= 10; j++)
            setHint(u, j, (v >> (j - 1) & 1));
 
        for (int j = 11; j <= 20; j++)
            setHint(u, j, (parent[u] >> (j - 11) & 1));
    }
}
 
int nxt[MAXN], par[MAXN];
bool passed[MAXN];
int cnt = 0;
int tot;
 
void solve(int u, int go) {
    // cout << u << ' ' << go << endl;
    assert(u && u <= tot);
    if (!passed[u]) {
        passed[u] = 1;
        cnt++;
        for (int j = 0; j < 10; j++)
            nxt[u] |= (getHint(j + 1) << j);
 
        for (int j = 0; j < 10; j++) 
            par[u] |= (getHint(j + 11) << j);
 
        if (!passed[nxt[u]]) go = nxt[u];
    }
 
    // if (cnt == tot) return;

    if (!go || !goTo(go)) {
        if (!par[u]) return;
        goTo(par[u]), solve(par[u], go);
    }
    else solve(go, 0);
}
 
void speedrun(int sub, int n, int start) {
    tot = n;
    solve(start, 0);
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 660 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 704 KB Output is correct
2 Incorrect 217 ms 660 KB Solution didn't visit every node

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 660 KB Output is correct
2 Correct 158 ms 704 KB Output is correct
3 Correct 211 ms 736 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 712 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 676 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -