QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#777321	#2810. Speedrun	linusvdv^#	21	492ms	4088kb	C++14	3.2kb	2024-11-24 00:41:32	2024-11-24 00:41:32

Judging History

你现在查看的是最新测评结果

[2024-11-24 00:41:32]
评测

测评结果：21
用时：492ms
内存：4088kb

查看

[2024-11-24 00:41:32]
提交

speedrun

#include "speedrun.h"
#include <cstdlib>
#include <vector>
#include <unistd.h>


void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    if (subtask==1) {
        setHintLen(N);
        for (int i = 1; i < N; i++) {
            setHint(A[i], B[i], true);
            setHint(B[i], A[i], true);
        }
    }
    else if (subtask==2) {
        setHintLen(5);
        std::vector<int> num(N+1, 0);
        for (int i = 1; i < N; i++) {
            num[A[i]]++;
            num[B[i]]++;
        }
        for (int i = 1; i <= N; i++) {
            if (num[i] > 1) {
                setHint(i, 1, true);
            }
        }
        if (N <= 2) {
            setHint(1, 1, true);
        }
    }
    else if (subtask==3) {
        setHintLen(20);
        std::vector<std::pair<int, int>> connections(N+1, {0, 0});
        for(int i = 1; i < N; i++) {
            if (connections[A[i]].first != 0) {
                connections[A[i]].first = B[i];
            }
            else {
                connections[A[i]].second = B[i];
            }
            if (connections[B[i]].first != 0) {
                connections[B[i]].first = A[i];
            }
            else {
                connections[B[i]].second = A[i];
            }
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < 5; j++) {
                setHint(i, j+1, bool(connections[i].first & 1));
                connections[i].first>>=1;
                setHint(i, j+6, bool(connections[i].second& 1));
                connections[i].second>>=1;
            }
        }
    }
}


void SolveRec(std::vector<bool>& visited, int current, int last, int N) {
    visited[current] = true;
    for (int i = 1; i <= N; i++) {
        if (visited[i]) {
            continue;
        }
        if(getHint(i)) {
            if(!goTo(i)) {
                exit(-1);
            }
            SolveRec(visited, i, current, N);
        }
    }
    if (last != -1) {
        if(!goTo(last)) {
            exit(-1);
        }
    }
}

void SolveRec3(std::vector<bool>& visited, int current, int last, int N) {
    visited[current] = true;
    int a=0;
    int b=0;
    for (int j = 4; j >= 0; j++) {
        a <<=1;
        b <<=1;
        a |= getHint(j+1);
        b |= getHint(j+6);
    }
    if (a != 0 && !visited[a]) {
        goTo(a);
        SolveRec3(visited, a, current, N);
    }
    if (b != 0 && !visited[b]) {
        goTo(b);
        SolveRec3(visited, b, current, N);
    }
    if (last != -1) {
        if(!goTo(last)) {
            exit(-1);
        }
    }
}


void speedrun(int subtask, int N, int start) { /* your solution here */
    if (subtask==1) {
        std::vector<bool> visited(N+1, false);
        getLength();
        SolveRec(visited, start, -1, N);
    }
    else if (subtask==2) {
        int center = -1;
        getLength();
        for (int i = 1; i <= N; i++) {
            goTo(i);
            if(getHint(1)) {
                center = i;
                continue;
            }
        }
        for (int i = 1; i <= N; i++) {
            goTo(i);
            goTo(center);
        }
    }
    else if (subtask==3) {
        std::vector<bool> visited(N+1, false);
        getLength();
        SolveRec3(visited, start, -1, N);
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 21

Accepted

Test #1:

score: 21

Accepted

time: 492ms

memory: 3792kb

input:

output:

1 1 1000
1 2 1 119 1
1 2 119 1 1
1 2 1 453 1
1 2 453 1 1
1 2 1 454 1
1 2 454 1 1
1 2 2 59 1
1 2 59 2 1
1 2 3 113 1
1 2 113 3 1
1 2 3 657 1
1 2 657 3 1
1 2 3 824 1
1 2 824 3 1
1 2 4 494 1
1 2 494 4 1
1 2 5 33 1
1 2 33 5 1
1 2 5 550 1
1 2 550 5 1
1 2 5 937 1
1 2 937 5 1
1 2 6 287 1
1 2 287 6 1
1 2 7 2...

input:

output:

result:

ok OK

Test #2:

score: 21

Accepted

time: 454ms

memory: 3804kb

input:

output:

1 1 1000
1 2 1 723 1
1 2 723 1 1
1 2 1 992 1
1 2 992 1 1
1 2 2 372 1
1 2 372 2 1
1 2 2 542 1
1 2 542 2 1
1 2 3 692 1
1 2 692 3 1
1 2 4 692 1
1 2 692 4 1
1 2 5 693 1
1 2 693 5 1
1 2 5 807 1
1 2 807 5 1
1 2 6 390 1
1 2 390 6 1
1 2 6 829 1
1 2 829 6 1
1 2 7 692 1
1 2 692 7 1
1 2 8 692 1
1 2 692 8 1
1 2...

input:

output:

result:

ok OK

Test #3:

score: 21

Accepted

time: 489ms

memory: 3720kb

input:

output:

1 1 1000
1 2 1 14 1
1 2 14 1 1
1 2 1 139 1
1 2 139 1 1
1 2 1 817 1
1 2 817 1 1
1 2 1 975 1
1 2 975 1 1
1 2 2 840 1
1 2 840 2 1
1 2 2 993 1
1 2 993 2 1
1 2 3 207 1
1 2 207 3 1
1 2 4 367 1
1 2 367 4 1
1 2 4 847 1
1 2 847 4 1
1 2 4 977 1
1 2 977 4 1
1 2 5 18 1
1 2 18 5 1
1 2 6 9 1
1 2 9 6 1
1 2 6 667 1...

input:

output:

result:

ok OK

Test #4:

score: 21

Accepted

time: 386ms

memory: 4088kb

input:

output:

1 1 1000
1 2 1 504 1
1 2 504 1 1
1 2 1 638 1
1 2 638 1 1
1 2 1 792 1
1 2 792 1 1
1 2 1 941 1
1 2 941 1 1
1 2 2 133 1
1 2 133 2 1
1 2 3 664 1
1 2 664 3 1
1 2 4 188 1
1 2 188 4 1
1 2 4 341 1
1 2 341 4 1
1 2 4 685 1
1 2 685 4 1
1 2 5 385 1
1 2 385 5 1
1 2 5 561 1
1 2 561 5 1
1 2 5 881 1
1 2 881 5 1
1 2...

input:

output:

result:

ok OK

Subtask #2:

score: 0

Wrong Answer

Test #5:

score: 0

Wrong Answer

time: 12ms

memory: 3776kb

input:

output:

1 1 5
1 2 133 1 1

input:

output:

result:

wrong answer Solution didn't visit every node

Subtask #3:

score: 0

Time Limit Exceeded

Test #7:

score: 0

Time Limit Exceeded

input:

output:

input:

output:

result:

wrong answer Invalid bit index for getHint

Subtask #4:

score: 0

Wrong Answer

Test #10:

score: 0

Wrong Answer

time: 1ms

memory: 3668kb

input:

output:

input:

2
4 1000 196

output:

result:

wrong answer Solution didn't visit every node

Subtask #5:

score: 0

Wrong Answer

Test #16:

score: 0

Wrong Answer

time: 1ms

memory: 3592kb

input:

output:

input:

2
5 1000 274

output:

result:

wrong answer Solution didn't visit every node