oj.uz

Submission #850762

# Submission time Handle Problem Language Result Execution time Memory
850762 2023-09-17T11:50:28 Z Itamar Speedrun (RMI21_speedrun) C++14
100 / 100
 1607 ms 2096 KB 
#define pi pair<int,int>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define vi vector<int>
#include "speedrun.h"
using namespace std;
void seth(int i, pi p) {
    for (int j = 1; j <= 10; j++) {
        setHint(i, j, p.first % 2);
        p.first /= 2;
    }
    for (int j = 11; j <= 20; j++) {
        setHint(i, j, p.second % 2);
        p.second /= 2;
    }
}
pi get() {
    pi ans;
    int j = 1;
    for (int i = 1; i < 1024; i*=2) {
        ans.first += getHint(j) * i;
        j++;
    }
    for (int i = 1; i < 1024; i *= 2) {
        ans.second += getHint(j) * i;
        j++;
    }
    return ans;
}
void dfs(int i, vi&pad, vector<vi>&fr) {
    for (int f : fr[i]) {
        if (f != pad[i]) {
            pad[f] = i;
            dfs(f,pad,fr);
        }
    }
}
#include <queue>
void assignHints(int subtask, int N, int A[], int B[]) {
    /* your solution here */
    setHintLen(20);
    if (N == 1)return;
    vector<vi> fr(N + 1);
    for (int i = 1; i < N; i++) {
        fr[A[i]].push_back(B[i]);
        fr[B[i]].push_back(A[i]);
    }
    vi pad(N + 1);
    vector<vi> son(N + 1);
    dfs(1, pad, fr);
    for (int i = 2; i <= N; i++) {
        son[pad[i]].push_back(i);
    }
    /*for (int i = 1; i <= N; i++) {
        if (son[i].empty())son[i].push_back(0);
    }*/
    vi v;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        v.push_back(i);
        for (int f : son[i]) {
            q.push(f);
        }
    }
    v.push_back(0);
    for (int i = 0; i < N; i++) {
        seth(v[i], { pad[v[i]],v[i + 1] });
    }/*
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < son[i].size(); j++) {
            int s = son[i][j];
            if (s == 0)break;
            if (s == son[i].back()) {
                seth(s, { son[s][0],i });
            }
            else {
                seth(s, { son[s][0],son[i][j + 1] });
            }
        }
    }
    seth(1, { son[1][0],0 });*/
}
void walk(int a, int b, vi&pad, vi&h) {
    int l;
    int x = a, y = b;
    if (h[x] > h[y])swap(x, y);
    while (h[y] > h[x]) {
        y = pad[y];
    }
    while (x != y) {
        x = pad[x], y = pad[y];
    }
    l = x;
    while (a != l) {
        pi p = get();
        a = p.first;
        goTo(p.first);
    }
    vi v={b};
    while (b != l) {
        v.push_back(pad[b]);
        b = pad[b];
    }
    for (int i = v.size() - 2; i >= 0; i--) {
        goTo(v[i]);
    }
}
void speedrun(int subtask, int N, int start) {
    if (N == 1)return;
    int x = start;
    while (x != 1) {
        pi p = get();
        x = p.first;
        goTo(p.first);
    }
    vi v = { 1 };
    int it = 0;
    vi h(N + 1);
    vi pad(N + 1);
    for (int i = 0; i < N - 1; i++) {
        v.push_back(get().second);
        
        while (true) {
            walk(x, v[it], pad,h);
            x = v[it];
            if (goTo(v.back())) {
                x = v.back();
                pad[x] = v[it];
                h[x] = h[v[it]] + 1;
                break;
            }
            else it++;
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1584 KB Output is correct
2 Correct 143 ms 1076 KB Output is correct
3 Correct 157 ms 1376 KB Output is correct
4 Correct 450 ms 1220 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1332 KB Output is correct
2 Correct 106 ms 1492 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 1472 KB Output is correct
2 Correct 1607 ms 1204 KB Output is correct
3 Correct 1432 ms 1332 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 1336 KB Output is correct
2 Correct 130 ms 1856 KB Output is correct
3 Correct 123 ms 1332 KB Output is correct
4 Correct 423 ms 1460 KB Output is correct
5 Correct 143 ms 2096 KB Output is correct
6 Correct 91 ms 1336 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 1728 KB Output is correct
2 Correct 109 ms 1256 KB Output is correct
3 Correct 122 ms 1352 KB Output is correct
4 Correct 252 ms 1228 KB Output is correct
5 Correct 143 ms 1500 KB Output is correct
6 Correct 150 ms 1440 KB Output is correct
7 Correct 115 ms 1100 KB Output is correct