QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#21224	#2810. Speedrun	Qingyu	72	36ms	4032kb	C++20	4.0kb	2022-03-03 19:57:11	2024-06-05 09:12:03

Judging History

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

[2024-06-05 09:12:03]
管理员手动重测本题所有提交记录

测评结果：72
用时：36ms
内存：4032kb

查看

[2024-05-20 18:51:06]
管理员手动重测本题所有提交记录

测评结果：72
用时：36ms
内存：4120kb

查看

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-01-17 10:50:26]
评测

测评结果：21
用时：152ms
内存：3712kb

查看

[2022-03-03 19:57:11]
提交

speedrun

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;
 
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}
 
#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map
 
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}
 
 
 
#include "speedrun.h"
 
vvi g;
vi ord;
void set1(int i,int x){
    for(int j=0; j<10; j++)
        if(x&(1<<j))
            setHint(i,j+1,1);
}
void set2(int i,int x){
    for(int j=0; j<10; j++)
        if(x&(1<<j))
            setHint(i,j+10+1,1);
}
 
void dfsp(int src,int par){
    if(par!=-1)
        set2(src,par);
    ord.pb(src);
    for(int nbr:g[src])
        if(nbr!=par)
            dfsp(nbr,src);
}
void assignHints(int subtask, int n, int A[], int B[]) {
    g.resize(n+1);
    for(int i=1; i<n; i++){
        g[A[i]].pb(B[i]);
        g[B[i]].pb(A[i]);
    }
 
    setHintLen(21);
    dfsp(1,-1);
 
    set2(1,ord.back());
    for(int i=0; i<n; i++){
        set1(ord[i],ord[(i+1)%ord.size()]);
    }
    for(int i=2; i<=n; i++)
        setHint(i,21,g[i].size()==1);
}
 
int get(int ix){
    int ans=0;
    for(int i=0; i<10; i++)
        if(getHint(1+i+10*ix))
            ans+=(1<<i);
    return ans;
}
 
stack<int>nxt;
vector<bool>vis;
void dfs(int src,int par){
    int cnxt=get(0),cprv=get(1);
    vis[src]=1;
    if(getHint(21) && !vis[cnxt])
        nxt.push(cnxt);
 
    while(!getHint(21)){
        bool ok=0;
        while(nxt.size() && !vis[nxt.top()] && goTo(nxt.top())){
            int t=nxt.top();
            nxt.pop();
            dfs(t,src);
            ok=1;
        }
        if(!vis[cnxt] && goTo(cnxt)) {
            dfs(cnxt, src);
            if(!nxt.size())
                break;
            cnxt=nxt.top();
            ok=1;
        }
        if(!ok)break;
    }
    if(!vis[cprv] && goTo(cprv))
        dfs(cprv,src);
    if(par!=-1)
        goTo(par);
}
 
void speedrun(int subtask, int N, int start) {
    vis.resize(N+1);
    dfs(start,-1);
    bool ok=1;
}
/*
5
1 2
1 3
3 4
3 5
 
5
1 2
1 3
1 4
1 5
 
7
1 2
1 3
2 4
2 5
3 6
3 7
 
18
1 2
1 3
2 4
2 5
3 6
3 7
5 8
6 9
6 10
1 11
3 12
12 13
8 14
14 15
15 16
16 17
1 18
 */

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 21

Accepted

Test #1:

score: 21

Accepted

time: 14ms

memory: 3776kb

input:

output:

1 1 21
1 2 119 11 1
1 2 295 11 1
1 2 295 12 1
1 2 295 13 1
1 2 295 15 1
1 2 295 16 1
1 2 295 17 1
1 2 735 11 1
1 2 735 12 1
1 2 735 13 1
1 2 735 16 1
1 2 735 19 1
1 2 785 11 1
1 2 785 12 1
1 2 785 13 1
1 2 785 14 1
1 2 785 15 1
1 2 785 17 1
1 2 785 18 1
1 2 785 20 1
1 2 164 11 1
1 2 164 15 1
1 2 164...

input:

output:

result:

ok OK

Test #2:

score: 21

Accepted

time: 9ms

memory: 3804kb

input:

output:

1 1 21
1 2 723 11 1
1 2 289 11 1
1 2 289 12 1
1 2 289 15 1
1 2 289 17 1
1 2 289 18 1
1 2 289 20 1
1 2 129 11 1
1 2 129 16 1
1 2 129 19 1
1 2 115 11 1
1 2 115 18 1
1 2 395 11 1
1 2 395 12 1
1 2 395 15 1
1 2 395 16 1
1 2 395 17 1
1 2 794 11 1
1 2 794 12 1
1 2 794 14 1
1 2 794 18 1
1 2 794 19 1
1 2 953...

input:

output:

result:

ok OK

Test #3:

score: 21

Accepted

time: 22ms

memory: 3784kb

input:

output:

1 1 21
1 2 14 11 1
1 2 620 12 1
1 2 620 13 1
1 2 620 14 1
1 2 49 13 1
1 2 49 14 1
1 2 49 16 1
1 2 49 17 1
1 2 49 20 1
1 2 936 12 1
1 2 936 13 1
1 2 936 14 1
1 2 991 14 1
1 2 991 16 1
1 2 991 18 1
1 2 991 19 1
1 2 991 20 1
1 2 139 11 1
1 2 166 11 1
1 2 166 12 1
1 2 166 14 1
1 2 166 18 1
1 2 738 11 1
...

input:

output:

result:

ok OK

Test #4:

score: 21

Accepted

time: 13ms

memory: 3792kb

input:

output:

1 1 21
1 2 504 11 1
1 2 638 11 1
1 2 681 12 1
1 2 681 13 1
1 2 681 14 1
1 2 681 15 1
1 2 681 16 1
1 2 681 17 1
1 2 681 20 1
1 2 451 11 1
1 2 451 14 1
1 2 451 16 1
1 2 451 18 1
1 2 451 20 1
1 2 466 11 1
1 2 466 14 1
1 2 466 16 1
1 2 466 18 1
1 2 466 20 1
1 2 391 12 1
1 2 391 15 1
1 2 391 17 1
1 2 391...

input:

output:

result:

ok OK

Subtask #2:

score: 0

Wrong Answer

Test #5:

score: 0

Wrong Answer

time: 1ms

memory: 4032kb

input:

output:

1 1 21

input:

output:

result:

wrong answer Solution didn't visit every node

Subtask #3:

score: 0

Wrong Answer

Test #7:

score: 0

Wrong Answer

time: 1ms

memory: 3772kb

input:

output:

1 1 21

input:

output:

result:

wrong answer Solution didn't visit every node

Subtask #4:

score: 12

Accepted

Test #10:

score: 12

Accepted

time: 29ms

memory: 4032kb

input:

output:

1 1 21
1 2 103 11 1
1 2 560 11 1
1 2 560 12 1
1 2 560 13 1
1 2 560 16 1
1 2 560 17 1
1 2 803 11 1
1 2 803 12 1
1 2 803 13 1
1 2 803 16 1
1 2 803 17 1
1 2 534 11 1
1 2 534 12 1
1 2 534 16 1
1 2 534 19 1
1 2 534 20 1
1 2 18 12 1
1 2 18 13 1
1 2 18 15 1
1 2 18 20 1
1 2 500 12 1
1 2 500 15 1
1 2 768 12 ...

input:

output:

result:

ok OK

Test #11:

score: 12

Accepted

time: 22ms

memory: 3764kb

input:

output:

1 1 21
1 2 324 11 1
1 2 451 13 1
1 2 451 17 1
1 2 451 19 1
1 2 830 13 1
1 2 830 17 1
1 2 830 19 1
1 2 458 11 1
1 2 72 12 1
1 2 72 14 1
1 2 72 17 1
1 2 72 18 1
1 2 72 19 1
1 2 390 14 1
1 2 390 17 1
1 2 778 12 1
1 2 778 13 1
1 2 778 18 1
1 2 778 19 1
1 2 374 12 1
1 2 374 14 1
1 2 374 19 1
1 2 374 20 1...

input:

output:

result:

ok OK

Test #12:

score: 12

Accepted

time: 16ms

memory: 4028kb

input:

output:

1 1 21
1 2 520 11 1
1 2 50 14 1
1 2 50 20 1
1 2 93 14 1
1 2 93 20 1
1 2 107 14 1
1 2 107 20 1
1 2 143 14 1
1 2 143 20 1
1 2 148 14 1
1 2 148 20 1
1 2 149 14 1
1 2 149 20 1
1 2 151 14 1
1 2 151 20 1
1 2 196 14 1
1 2 196 20 1
1 2 199 14 1
1 2 199 20 1
1 2 204 14 1
1 2 204 20 1
1 2 215 14 1
1 2 215 20 ...

input:

output:

result:

ok OK

Test #13:

score: 12

Accepted

time: 18ms

memory: 3796kb

input:

output:

1 1 21
1 2 975 11 1
1 2 555 11 1
1 2 555 12 1
1 2 555 13 1
1 2 555 14 1
1 2 555 17 1
1 2 555 18 1
1 2 555 19 1
1 2 555 20 1
1 2 316 11 1
1 2 316 12 1
1 2 316 14 1
1 2 316 16 1
1 2 316 20 1
1 2 373 13 1
1 2 373 14 1
1 2 373 15 1
1 2 373 16 1
1 2 373 19 1
1 2 570 11 1
1 2 570 13 1
1 2 570 15 1
1 2 570...

input:

output:

result:

ok OK

Test #14:

score: 12

Accepted

time: 21ms

memory: 3756kb

input:

output:

1 1 21
1 2 61 11 1
1 2 35 11 1
1 2 35 13 1
1 2 35 14 1
1 2 35 15 1
1 2 35 16 1
1 2 184 11 1
1 2 184 12 1
1 2 184 16 1
1 2 113 14 1
1 2 113 15 1
1 2 113 16 1
1 2 113 18 1
1 2 247 11 1
1 2 247 15 1
1 2 247 16 1
1 2 247 17 1
1 2 607 11 1
1 2 607 12 1
1 2 607 13 1
1 2 607 15 1
1 2 607 16 1
1 2 607 17 1
...

input:

output:

result:

ok OK

Test #15:

score: 12

Accepted

time: 18ms

memory: 3828kb

input:

output:

1 1 21
1 2 820 11 1
1 2 2 13 1
1 2 2 15 1
1 2 2 16 1
1 2 2 19 1
1 2 2 20 1
1 2 3 13 1
1 2 3 15 1
1 2 3 16 1
1 2 3 19 1
1 2 3 20 1
1 2 4 13 1
1 2 4 15 1
1 2 4 16 1
1 2 4 19 1
1 2 4 20 1
1 2 5 13 1
1 2 5 15 1
1 2 5 16 1
1 2 5 19 1
1 2 5 20 1
1 2 6 13 1
1 2 6 15 1
1 2 6 16 1
1 2 6 19 1
1 2 6 20 1
1 2 7...

input:

output:

result:

ok OK

Subtask #5:

score: 39

Acceptable Answer

Test #16:

score: 39

Acceptable Answer

time: 15ms

memory: 3768kb

input:

output:

1 1 21
1 2 296 11 1
1 2 496 14 1
1 2 496 16 1
1 2 496 19 1
1 2 945 15 1
1 2 945 16 1
1 2 945 17 1
1 2 945 18 1
1 2 945 19 1
1 2 768 14 1
1 2 768 16 1
1 2 768 19 1
1 2 39 19 1
1 2 39 20 1
1 2 873 14 1
1 2 873 16 1
1 2 873 19 1
1 2 109 11 1
1 2 109 14 1
1 2 109 16 1
1 2 109 17 1
1 2 109 19 1
1 2 109 2...

input:

output:

result:

points 0.9750 points  0.9750 Partial solution

Test #17:

score: 39

Acceptable Answer

time: 36ms

memory: 3772kb

input:

output:

1 1 21
1 2 266 11 1
1 2 101 12 1
1 2 101 14 1
1 2 101 19 1
1 2 66 11 1
1 2 66 13 1
1 2 66 16 1
1 2 66 17 1
1 2 87 12 1
1 2 87 17 1
1 2 458 11 1
1 2 458 12 1
1 2 458 13 1
1 2 458 15 1
1 2 458 17 1
1 2 44 12 1
1 2 44 14 1
1 2 44 17 1
1 2 44 18 1
1 2 44 19 1
1 2 884 13 1
1 2 884 14 1
1 2 884 16 1
1 2 3...

input:

output:

result:

points 0.9750 points  0.9750 Partial solution

Test #18:

score: 39

Acceptable Answer

time: 31ms

memory: 3716kb

input:

output:

1 1 21
1 2 76 11 1
1 2 31 13 1
1 2 31 14 1
1 2 31 17 1
1 2 70 13 1
1 2 70 14 1
1 2 70 17 1
1 2 72 13 1
1 2 72 14 1
1 2 72 17 1
1 2 179 13 1
1 2 179 14 1
1 2 179 17 1
1 2 180 13 1
1 2 180 14 1
1 2 180 17 1
1 2 185 13 1
1 2 185 14 1
1 2 185 17 1
1 2 211 13 1
1 2 211 14 1
1 2 211 17 1
1 2 225 13 1
1 2 ...

input:

output:

result:

points 0.9750 points  0.9750 Partial solution

Test #19:

score: 39

Acceptable Answer

time: 26ms

memory: 3764kb

input:

output:

1 1 21
1 2 315 11 1
1 2 857 11 1
1 2 857 12 1
1 2 857 14 1
1 2 857 15 1
1 2 857 16 1
1 2 857 19 1
1 2 301 11 1
1 2 301 14 1
1 2 301 15 1
1 2 301 17 1
1 2 301 19 1
1 2 301 20 1
1 2 456 11 1
1 2 456 13 1
1 2 456 14 1
1 2 456 16 1
1 2 456 19 1
1 2 874 14 1
1 2 874 17 1
1 2 874 18 1
1 2 874 19 1
1 2 313...

input:

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

output:

result:

points 0.9750 points  0.9750 Partial solution

Test #20:

score: 39

Acceptable Answer

time: 15ms

memory: 3832kb

input:

output:

1 1 21
1 2 565 11 1
1 2 35 11 1
1 2 35 13 1
1 2 35 15 1
1 2 35 16 1
1 2 35 20 1
1 2 378 11 1
1 2 378 12 1
1 2 378 16 1
1 2 493 11 1
1 2 493 12 1
1 2 493 16 1
1 2 727 11 1
1 2 727 12 1
1 2 727 16 1
1 2 915 11 1
1 2 915 12 1
1 2 915 16 1
1 2 48 11 1
1 2 48 13 1
1 2 48 15 1
1 2 48 16 1
1 2 48 20 1
1 2 ...

input:

output:

result:

points 0.9750 points  0.9750 Partial solution

Test #21:

score: 39

Acceptable Answer

time: 29ms

memory: 3748kb

input:

output:

1 1 21
1 2 205 11 1
1 2 874 11 1
1 2 874 13 1
1 2 874 14 1
1 2 874 17 1
1 2 874 18 1
1 2 275 12 1
1 2 275 14 1
1 2 275 16 1
1 2 275 17 1
1 2 275 19 1
1 2 275 20 1
1 2 99 11 1
1 2 99 12 1
1 2 99 15 1
1 2 99 19 1
1 2 98 11 1
1 2 98 12 1
1 2 98 16 1
1 2 98 17 1
1 2 273 12 1
1 2 273 16 1
1 2 273 17 1
1 ...

input:

output:

result:

points 0.9750 points  0.9750 Partial solution

Test #22:

score: 39

Acceptable Answer

time: 18ms

memory: 3764kb

input:

output:

1 1 21
1 2 537 11 1
1 2 2 11 1
1 2 2 14 1
1 2 2 15 1
1 2 2 20 1
1 2 3 11 1
1 2 3 14 1
1 2 3 15 1
1 2 3 20 1
1 2 4 11 1
1 2 4 14 1
1 2 4 15 1
1 2 4 20 1
1 2 5 11 1
1 2 5 14 1
1 2 5 15 1
1 2 5 20 1
1 2 6 11 1
1 2 6 14 1
1 2 6 15 1
1 2 6 20 1
1 2 7 11 1
1 2 7 14 1
1 2 7 15 1
1 2 7 20 1
1 2 8 11 1
1 2 8...

input:

output:

result:

points 0.9750 points  0.9750 Partial solution