QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#778964	#2810. Speedrun	ChiFAN	100 ✓	41ms	3976kb	C++14	1.3kb	2024-11-24 16:55:13	2024-11-24 16:55:14

Judging History

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

[2024-11-24 16:55:14]
评测

测评结果：100
用时：41ms
内存：3976kb

查看

[2024-11-24 16:55:13]
提交

speedrun

#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;
const int maxn = 1e3+114;
vector<int> E[maxn];
int dfn[maxn],node[maxn],dfncnt;
int fa[maxn];
void dfs(int u){
    dfn[u]=++dfncnt;
    node[dfncnt]=u;
    for(int v:E[u]){
        if(v!=fa[u]){
            fa[v]=u;
            dfs(v);
        }
    }
}
void assignHints(int subtask, int N, int A[], int B[]){
    for(int i=1;i<N;i++) E[A[i]].push_back(B[i]),E[B[i]].push_back(A[i]);
    dfs(1);
    setHintLen(20);
    for(int i=1;i<=N;i++){
        for(int j=0;j<10;j++){
            if((1<<j)&fa[i]) setHint(i,j+1,1);
        }        
        for(int j=0;j<10;j++){
            if((1<<j)&node[dfn[i]+1]) setHint(i,j+11,1);
        }
    }
}
void speedrun(int subtask, int N, int start ){
    int now=start;
    while(now!=1){
        int to=0;
        for(int j=0;j<10;j++) to+=(1<<j)*getHint(j+1);
        goTo(to);
        now=to;
    }
    int nxt=0;
    for(int j=0;j<10;j++) nxt+=(1<<j)*getHint(j+11);
    while(nxt!=0){
        while(goTo(nxt)==false){
            //跳回父亲
            int lst=0;
            for(int j=0;j<10;j++) lst+=(1<<j)*getHint(j+1);
            goTo(lst);
        }
        now=nxt;
        //确定 dfn 序上下一个点
        nxt=0;
        for(int j=0;j<10;j++) nxt+=(1<<j)*getHint(j+11);
    }
    return ;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 21

Accepted

Test #1:

score: 21

Accepted

time: 18ms

memory: 3912kb

input:

output:

1 1 20
1 2 1 11 1
1 2 1 12 1
1 2 1 13 1
1 2 1 15 1
1 2 1 16 1
1 2 1 17 1
1 2 2 1 1
1 2 2 2 1
1 2 2 4 1
1 2 2 5 1
1 2 2 6 1
1 2 2 13 1
1 2 2 15 1
1 2 2 16 1
1 2 2 17 1
1 2 2 19 1
1 2 3 1 1
1 2 3 5 1
1 2 3 6 1
1 2 3 7 1
1 2 3 11 1
1 2 3 15 1
1 2 3 18 1
1 2 3 20 1
1 2 4 2 1
1 2 4 3 1
1 2 4 4 1
1 2 4 6 ...

input:

output:

result:

ok OK

Test #2:

score: 21

Accepted

time: 38ms

memory: 3968kb

input:

output:

1 1 20
1 2 1 11 1
1 2 1 12 1
1 2 1 15 1
1 2 1 17 1
1 2 1 18 1
1 2 1 20 1
1 2 2 3 1
1 2 2 5 1
1 2 2 6 1
1 2 2 7 1
1 2 2 9 1
1 2 2 12 1
1 2 2 13 1
1 2 2 14 1
1 2 2 15 1
1 2 2 20 1
1 2 3 3 1
1 2 3 5 1
1 2 3 6 1
1 2 3 8 1
1 2 3 10 1
1 2 3 13 1
1 2 4 3 1
1 2 4 5 1
1 2 4 6 1
1 2 4 8 1
1 2 4 10 1
1 2 4 11 ...

input:

output:

result:

ok OK

Test #3:

score: 21

Accepted

time: 29ms

memory: 3888kb

input:

output:

input:

output:

result:

ok OK

Test #4:

score: 21

Accepted

time: 21ms

memory: 3904kb

input:

output:

input:

output:

result:

ok OK

Subtask #2:

score: 8

Accepted

Test #5:

score: 8

Accepted

time: 15ms

memory: 3816kb

input:

output:

input:

output:

result:

ok OK

Test #6:

score: 8

Accepted

time: 41ms

memory: 3836kb

input:

output:

input:

output:

result:

ok OK

Subtask #3:

score: 19

Accepted

Test #7:

score: 19

Accepted

time: 23ms

memory: 3888kb

input:

output:

input:

output:

result:

ok OK

Test #8:

score: 19

Accepted

time: 36ms

memory: 3832kb

input:

output:

1 1 20
1 2 1 15 1
1 2 1 16 1
1 2 1 17 1
1 2 1 18 1
1 2 2 2 1
1 2 2 3 1
1 2 2 5 1
1 2 2 8 1
1 2 2 13 1
1 2 2 14 1
1 2 2 15 1
1 2 2 16 1
1 2 2 19 1
1 2 3 1 1
1 2 3 3 1
1 2 3 4 1
1 2 3 5 1
1 2 3 6 1
1 2 3 10 1
1 2 3 12 1
1 2 3 13 1
1 2 3 14 1
1 2 3 15 1
1 2 3 16 1
1 2 4 1 1
1 2 4 3 1
1 2 4 6 1
1 2 4 12...

input:

output:

result:

ok OK

Test #9:

score: 19

Accepted

time: 28ms

memory: 3828kb

input:

output:

1 1 20
1 2 1 11 1
1 2 1 12 1
1 2 1 14 1
1 2 1 18 1
1 2 1 19 1
1 2 2 2 1
1 2 2 5 1
1 2 2 6 1
1 2 2 8 1
1 2 2 9 1
1 2 2 16 1
1 2 2 19 1
1 2 3 3 1
1 2 3 4 1
1 2 3 6 1
1 2 3 8 1
1 2 3 11 1
1 2 3 12 1
1 2 3 13 1
1 2 3 14 1
1 2 3 17 1
1 2 3 18 1
1 2 3 19 1
1 2 4 2 1
1 2 4 3 1
1 2 4 4 1
1 2 4 11 1
1 2 4 12...

input:

output:

result:

ok OK

Subtask #4:

score: 12

Accepted

Test #10:

score: 12

Accepted

time: 30ms

memory: 3968kb

input:

output:

input:

output:

result:

ok OK

Test #11:

score: 12

Accepted

time: 36ms

memory: 3864kb

input:

output:

input:

output:

result:

ok OK

Test #12:

score: 12

Accepted

time: 34ms

memory: 3812kb

input:

output:

input:

output:

result:

ok OK

Test #13:

score: 12

Accepted

time: 22ms

memory: 3832kb

input:

output:

input:

output:

result:

ok OK

Test #14:

score: 12

Accepted

time: 25ms

memory: 3976kb

input:

output:

1 1 20
1 2 1 11 1
1 2 1 13 1
1 2 1 14 1
1 2 1 15 1
1 2 1 16 1
1 2 2 1 1
1 2 2 2 1
1 2 2 3 1
1 2 2 4 1
1 2 2 5 1
1 2 2 6 1
1 2 2 7 1
1 2 2 9 1
1 2 2 11 1
1 2 2 12 1
1 2 2 17 1
1 2 3 1 1
1 2 3 3 1
1 2 3 4 1
1 2 3 7 1
1 2 3 8 1
1 2 3 9 1
1 2 3 10 1
1 2 3 14 1
1 2 3 15 1
1 2 3 17 1
1 2 3 19 1
1 2 3 20 1...

input:

output:

result:

ok OK

Test #15:

score: 12

Accepted

time: 13ms

memory: 3900kb

input:

output:

input:

output:

result:

ok OK

Subtask #5:

score: 40

Accepted

Test #16:

score: 40

Accepted

time: 31ms

memory: 3896kb

input:

output:

1 1 20
1 2 1 14 1
1 2 1 16 1
1 2 1 19 1
1 2 2 2 1
1 2 2 3 1
1 2 2 4 1
1 2 2 5 1
1 2 2 8 1
1 2 2 9 1
1 2 2 14 1
1 2 2 18 1
1 2 2 19 1
1 2 2 20 1
1 2 3 1 1
1 2 3 4 1
1 2 3 9 1
1 2 3 10 1
1 2 3 11 1
1 2 3 12 1
1 2 3 14 1
1 2 3 17 1
1 2 4 2 1
1 2 4 3 1
1 2 4 5 1
1 2 4 8 1
1 2 4 9 1
1 2 4 10 1
1 2 4 12 1...

input:

output:

result:

ok Partial solution

Test #17:

score: 40

Accepted

time: 10ms

memory: 3888kb

input:

output:

1 1 20
1 2 1 12 1
1 2 1 14 1
1 2 1 19 1
1 2 2 2 1
1 2 2 6 1
1 2 2 7 1
1 2 2 8 1
1 2 2 10 1
1 2 2 17 1
1 2 2 18 1
1 2 2 19 1
1 2 3 1 1
1 2 3 4 1
1 2 3 5 1
1 2 3 6 1
1 2 3 7 1
1 2 3 8 1
1 2 3 10 1
1 2 3 11 1
1 2 3 12 1
1 2 3 14 1
1 2 3 15 1
1 2 3 17 1
1 2 3 18 1
1 2 4 3 1
1 2 4 4 1
1 2 4 7 1
1 2 4 9 1...

input:

output:

result:

ok Partial solution

Test #18:

score: 40

Accepted

time: 11ms

memory: 3888kb

input:

output:

input:

output:

result:

ok Partial solution

Test #19:

score: 40

Accepted

time: 39ms

memory: 3828kb

input:

output:

input:

2
5 1000 1000
0
0
1
0
1
0
1
1
1
0
1
1
0
0
1
0
0
0
0
1
0
1
1
0
1
1
0
0
1
0
1
0
1
0
0
0
1
0
1
1
1
1
0
1
0
1
1
1
0
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
0
1
0
1
0
1
1
0
1
1
0
1
1
0
1
1
0
0
0
0
0
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
0
1
0
1
1
1
0
1
1
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
1
1
0
1
0
1
1
0
0
1
0
0
1
0
1
1
0
1
...

output:

result:

ok Partial solution

Test #20:

score: 40

Accepted

time: 38ms

memory: 3904kb

input:

output:

input:

output:

result:

ok Partial solution

Test #21:

score: 40

Accepted

time: 15ms

memory: 3928kb

input:

output:

input:

output:

result:

ok Partial solution

Test #22:

score: 40

Accepted

time: 5ms

memory: 3780kb

input:

output:

1 1 20
1 2 1 11 1
1 2 1 14 1
1 2 1 15 1
1 2 1 20 1
1 2 2 1 1
1 2 2 4 1
1 2 2 5 1
1 2 2 10 1
1 2 2 11 1
1 2 2 12 1
1 2 3 1 1
1 2 3 4 1
1 2 3 5 1
1 2 3 10 1
1 2 3 13 1
1 2 4 1 1
1 2 4 4 1
1 2 4 5 1
1 2 4 10 1
1 2 4 11 1
1 2 4 13 1
1 2 5 1 1
1 2 5 4 1
1 2 5 5 1
1 2 5 10 1
1 2 5 12 1
1 2 5 13 1
1 2 6 1 ...

input:

output:

result:

ok Partial solution