oj.uz

Submission #850716

# Submission time Handle Problem Language Result Execution time Memory
850716 2023-09-17T10:36:22 Z Itamar Speedrun (RMI21_speedrun) C++14
0 / 100
 265 ms 41260 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);
        }
    }
}
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);
    }
    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 speedrun(int subtask, int N, int start) {
    if (N == 1)return;
    int x = start;
    while (x != 1) {
        pi p = get();
        x = p.second;
        goTo(p.second);
    }
    vi vis1(N + 1);
    vi vis2(N + 1);
    x = get().first;
    int pad = 1;
    vi p(N + 1);
    goTo(get().first);
    p[x] = 1;
    while (x != 1) {
        if (!vis1[x] && get().first) {
            vis1[x] = 1;
            pad = x;
            x = get().first;
            p[x] = pad;
            goTo(get().first);
        }
        else {
            vis2[x] = 1;
            x = get().second;

            if (p[x])pad = p[x];
            else p[x] = pad;
            goTo(pad);
            goTo(x);
        }
    }
    return;
}

Compilation message

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

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 1332 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 1612 KB Output is correct
2 Incorrect 137 ms 1076 KB Used too many wrong interactions
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 41260 KB Output is correct
2 Correct 151 ms 35528 KB Output is correct
3 Incorrect 155 ms 37428 KB Used too many wrong interactions
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 4660 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 3640 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -