# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
566909 | 2022-05-23T06:11:26 Z | jamezzz | Jail (JOI22_jail) | C++17 | 5000 ms | 923844 KB |
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define dbg(...) printf(__VA_ARGS__); #define getchar_unlocked getchar #else #define dbg(...) #endif #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define li 2*i+1 #define ri 2*i+2 #define sz(x) (int)x.size() #define mnto(x,y) x=min(x,(__typeof__(x))y) #define mxto(x,y) x=max(x,(__typeof__(x))y) #define INF 1023456789 #define LINF 1023456789123456789 #define all(x) x.begin(), x.end() #define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin()); typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<pll> vll; mt19937 rng(time(0)); #define mod 1000000007 inline int rd(){ int x=0; char ch=getchar_unlocked(); while(!(ch&16))ch=getchar();//keep reading while current character is whitespace while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered x=(x<<3)+(x<<1)+(ch&15); ch=getchar_unlocked(); } return x; } #define maxn 120005 int n,m,s[maxn],t[maxn],sid[maxn],tid[maxn],deg[maxn]; int par[maxn],dep[maxn]; vi AL[maxn]; vector<iii> upds[maxn]; vi AL2[maxn],AL3[maxn]; void dfs(int u){ for(int v:AL[u]){ if(v==par[u])continue; par[v]=u; dep[v]=dep[u]+1; dfs(v); } } int main(){ int tc;sf("%d",&tc); while(tc--){ sf("%d",&n); for(int i=1;i<=n;++i){ sid[i]=tid[i]=-1; par[i]=0; AL[i].clear(); } for(int i=0;i<m;++i){ AL2[i].clear(); AL3[i].clear(); } for(int i=0;i<n-1;++i){ int a,b;sf("%d%d",&a,&b); AL[a].pb(b);AL[b].pb(a); } sf("%d",&m); for(int i=0;i<m;++i){ sf("%d%d",&s[i],&t[i]); sid[s[i]]=i; tid[t[i]]=i; } dfs(1); //AL2[u] -> v means v has to come before u for(int i=0;i<m;++i){ int u=s[i],v=t[i]; while(u!=v){ if(dep[u]<dep[v])swap(u,v); if(sid[u]!=-1&&sid[u]!=i){ AL2[i].pb(sid[u]); AL3[sid[u]].pb(i); } if(tid[u]!=-1&&tid[u]!=i){ AL2[tid[u]].pb(i); AL3[i].pb(tid[u]); } u=par[u]; } if(sid[v]!=-1&&sid[v]!=i){ AL2[i].pb(sid[v]); AL3[sid[v]].pb(i); } if(tid[v]!=-1&&tid[v]!=i){ AL2[tid[v]].pb(i); AL3[i].pb(tid[v]); } } vector<int> v; for(int i=0;i<m;++i){ disc(AL2[i]); disc(AL3[i]); deg[i]=AL2[i].size(); if(deg[i]==0)v.pb(i); } int proc=0; while(!v.empty()){ int x=v.back(); v.pop_back(); ++proc; for(int y:AL3[x]){ --deg[y]; if(deg[y]==0)v.pb(y); } } if(proc!=m)pf("No\n"); else pf("Yes\n"); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11604 KB | Output is correct |
2 | Correct | 6 ms | 11604 KB | Output is correct |
3 | Correct | 6 ms | 11544 KB | Output is correct |
4 | Correct | 16 ms | 11732 KB | Output is correct |
5 | Correct | 27 ms | 12160 KB | Output is correct |
6 | Correct | 8 ms | 11672 KB | Output is correct |
7 | Correct | 8 ms | 11604 KB | Output is correct |
8 | Correct | 11 ms | 11824 KB | Output is correct |
9 | Correct | 199 ms | 17348 KB | Output is correct |
10 | Correct | 234 ms | 28920 KB | Output is correct |
11 | Correct | 12 ms | 11732 KB | Output is correct |
12 | Correct | 98 ms | 12760 KB | Output is correct |
13 | Correct | 368 ms | 86840 KB | Output is correct |
14 | Correct | 596 ms | 114524 KB | Output is correct |
15 | Execution timed out | 5100 ms | 923844 KB | Time limit exceeded |
16 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11604 KB | Output is correct |
2 | Correct | 6 ms | 11604 KB | Output is correct |
3 | Correct | 7 ms | 11604 KB | Output is correct |
4 | Correct | 9 ms | 11604 KB | Output is correct |
5 | Correct | 9 ms | 11604 KB | Output is correct |
6 | Correct | 7 ms | 11604 KB | Output is correct |
7 | Correct | 7 ms | 11604 KB | Output is correct |
8 | Correct | 8 ms | 11552 KB | Output is correct |
9 | Correct | 7 ms | 11612 KB | Output is correct |
10 | Correct | 6 ms | 11604 KB | Output is correct |
11 | Correct | 7 ms | 11604 KB | Output is correct |
12 | Correct | 6 ms | 11588 KB | Output is correct |
13 | Correct | 6 ms | 11604 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11604 KB | Output is correct |
2 | Correct | 6 ms | 11604 KB | Output is correct |
3 | Correct | 7 ms | 11604 KB | Output is correct |
4 | Correct | 9 ms | 11604 KB | Output is correct |
5 | Correct | 9 ms | 11604 KB | Output is correct |
6 | Correct | 7 ms | 11604 KB | Output is correct |
7 | Correct | 7 ms | 11604 KB | Output is correct |
8 | Correct | 8 ms | 11552 KB | Output is correct |
9 | Correct | 7 ms | 11612 KB | Output is correct |
10 | Correct | 6 ms | 11604 KB | Output is correct |
11 | Correct | 7 ms | 11604 KB | Output is correct |
12 | Correct | 6 ms | 11588 KB | Output is correct |
13 | Correct | 6 ms | 11604 KB | Output is correct |
14 | Correct | 6 ms | 11604 KB | Output is correct |
15 | Correct | 6 ms | 11604 KB | Output is correct |
16 | Correct | 7 ms | 11520 KB | Output is correct |
17 | Correct | 7 ms | 11632 KB | Output is correct |
18 | Correct | 7 ms | 11604 KB | Output is correct |
19 | Correct | 7 ms | 11604 KB | Output is correct |
20 | Correct | 8 ms | 11660 KB | Output is correct |
21 | Correct | 8 ms | 11604 KB | Output is correct |
22 | Correct | 9 ms | 11592 KB | Output is correct |
23 | Correct | 7 ms | 11584 KB | Output is correct |
24 | Correct | 7 ms | 11604 KB | Output is correct |
25 | Correct | 7 ms | 11596 KB | Output is correct |
26 | Correct | 6 ms | 11604 KB | Output is correct |
27 | Correct | 7 ms | 11664 KB | Output is correct |
28 | Correct | 6 ms | 11604 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11604 KB | Output is correct |
2 | Correct | 6 ms | 11604 KB | Output is correct |
3 | Correct | 7 ms | 11604 KB | Output is correct |
4 | Correct | 9 ms | 11604 KB | Output is correct |
5 | Correct | 9 ms | 11604 KB | Output is correct |
6 | Correct | 7 ms | 11604 KB | Output is correct |
7 | Correct | 7 ms | 11604 KB | Output is correct |
8 | Correct | 8 ms | 11552 KB | Output is correct |
9 | Correct | 7 ms | 11612 KB | Output is correct |
10 | Correct | 6 ms | 11604 KB | Output is correct |
11 | Correct | 7 ms | 11604 KB | Output is correct |
12 | Correct | 6 ms | 11588 KB | Output is correct |
13 | Correct | 6 ms | 11604 KB | Output is correct |
14 | Correct | 6 ms | 11604 KB | Output is correct |
15 | Correct | 6 ms | 11604 KB | Output is correct |
16 | Correct | 7 ms | 11520 KB | Output is correct |
17 | Correct | 7 ms | 11632 KB | Output is correct |
18 | Correct | 7 ms | 11604 KB | Output is correct |
19 | Correct | 7 ms | 11604 KB | Output is correct |
20 | Correct | 8 ms | 11660 KB | Output is correct |
21 | Correct | 8 ms | 11604 KB | Output is correct |
22 | Correct | 9 ms | 11592 KB | Output is correct |
23 | Correct | 7 ms | 11584 KB | Output is correct |
24 | Correct | 7 ms | 11604 KB | Output is correct |
25 | Correct | 7 ms | 11596 KB | Output is correct |
26 | Correct | 6 ms | 11604 KB | Output is correct |
27 | Correct | 7 ms | 11664 KB | Output is correct |
28 | Correct | 6 ms | 11604 KB | Output is correct |
29 | Correct | 14 ms | 11884 KB | Output is correct |
30 | Correct | 8 ms | 11604 KB | Output is correct |
31 | Correct | 9 ms | 11724 KB | Output is correct |
32 | Correct | 8 ms | 11604 KB | Output is correct |
33 | Correct | 8 ms | 11664 KB | Output is correct |
34 | Correct | 8 ms | 11604 KB | Output is correct |
35 | Correct | 13 ms | 11724 KB | Output is correct |
36 | Correct | 8 ms | 11604 KB | Output is correct |
37 | Correct | 8 ms | 11676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11604 KB | Output is correct |
2 | Correct | 6 ms | 11604 KB | Output is correct |
3 | Correct | 7 ms | 11604 KB | Output is correct |
4 | Correct | 9 ms | 11604 KB | Output is correct |
5 | Correct | 9 ms | 11604 KB | Output is correct |
6 | Correct | 7 ms | 11604 KB | Output is correct |
7 | Correct | 7 ms | 11604 KB | Output is correct |
8 | Correct | 8 ms | 11552 KB | Output is correct |
9 | Correct | 7 ms | 11612 KB | Output is correct |
10 | Correct | 6 ms | 11604 KB | Output is correct |
11 | Correct | 7 ms | 11604 KB | Output is correct |
12 | Correct | 6 ms | 11588 KB | Output is correct |
13 | Correct | 6 ms | 11604 KB | Output is correct |
14 | Correct | 6 ms | 11604 KB | Output is correct |
15 | Correct | 6 ms | 11604 KB | Output is correct |
16 | Correct | 7 ms | 11520 KB | Output is correct |
17 | Correct | 7 ms | 11632 KB | Output is correct |
18 | Correct | 7 ms | 11604 KB | Output is correct |
19 | Correct | 7 ms | 11604 KB | Output is correct |
20 | Correct | 8 ms | 11660 KB | Output is correct |
21 | Correct | 8 ms | 11604 KB | Output is correct |
22 | Correct | 9 ms | 11592 KB | Output is correct |
23 | Correct | 7 ms | 11584 KB | Output is correct |
24 | Correct | 7 ms | 11604 KB | Output is correct |
25 | Correct | 7 ms | 11596 KB | Output is correct |
26 | Correct | 6 ms | 11604 KB | Output is correct |
27 | Correct | 7 ms | 11664 KB | Output is correct |
28 | Correct | 6 ms | 11604 KB | Output is correct |
29 | Correct | 14 ms | 11884 KB | Output is correct |
30 | Correct | 8 ms | 11604 KB | Output is correct |
31 | Correct | 9 ms | 11724 KB | Output is correct |
32 | Correct | 8 ms | 11604 KB | Output is correct |
33 | Correct | 8 ms | 11664 KB | Output is correct |
34 | Correct | 8 ms | 11604 KB | Output is correct |
35 | Correct | 13 ms | 11724 KB | Output is correct |
36 | Correct | 8 ms | 11604 KB | Output is correct |
37 | Correct | 8 ms | 11676 KB | Output is correct |
38 | Correct | 210 ms | 16616 KB | Output is correct |
39 | Correct | 249 ms | 28640 KB | Output is correct |
40 | Correct | 99 ms | 15308 KB | Output is correct |
41 | Correct | 32 ms | 12888 KB | Output is correct |
42 | Correct | 93 ms | 15444 KB | Output is correct |
43 | Correct | 30 ms | 13132 KB | Output is correct |
44 | Correct | 17 ms | 12148 KB | Output is correct |
45 | Correct | 61 ms | 18724 KB | Output is correct |
46 | Correct | 61 ms | 18588 KB | Output is correct |
47 | Correct | 74 ms | 22320 KB | Output is correct |
48 | Correct | 75 ms | 22388 KB | Output is correct |
49 | Correct | 57 ms | 18784 KB | Output is correct |
50 | Correct | 58 ms | 18708 KB | Output is correct |
51 | Correct | 53 ms | 18784 KB | Output is correct |
52 | Correct | 48 ms | 19752 KB | Output is correct |
53 | Correct | 15 ms | 12208 KB | Output is correct |
54 | Correct | 59 ms | 18648 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11604 KB | Output is correct |
2 | Correct | 6 ms | 11604 KB | Output is correct |
3 | Correct | 6 ms | 11520 KB | Output is correct |
4 | Correct | 6 ms | 11600 KB | Output is correct |
5 | Correct | 13 ms | 11604 KB | Output is correct |
6 | Correct | 7 ms | 11604 KB | Output is correct |
7 | Correct | 8 ms | 11592 KB | Output is correct |
8 | Correct | 7 ms | 11584 KB | Output is correct |
9 | Correct | 7 ms | 11612 KB | Output is correct |
10 | Correct | 7 ms | 11588 KB | Output is correct |
11 | Correct | 6 ms | 11592 KB | Output is correct |
12 | Correct | 7 ms | 11692 KB | Output is correct |
13 | Correct | 29 ms | 12136 KB | Output is correct |
14 | Correct | 32 ms | 12392 KB | Output is correct |
15 | Correct | 34 ms | 12344 KB | Output is correct |
16 | Correct | 65 ms | 19152 KB | Output is correct |
17 | Correct | 241 ms | 29036 KB | Output is correct |
18 | Correct | 643 ms | 68676 KB | Output is correct |
19 | Correct | 70 ms | 19048 KB | Output is correct |
20 | Correct | 63 ms | 18304 KB | Output is correct |
21 | Correct | 70 ms | 18216 KB | Output is correct |
22 | Correct | 203 ms | 31524 KB | Output is correct |
23 | Correct | 128 ms | 32072 KB | Output is correct |
24 | Correct | 164 ms | 30008 KB | Output is correct |
25 | Correct | 177 ms | 30088 KB | Output is correct |
26 | Correct | 202 ms | 32024 KB | Output is correct |
27 | Correct | 146 ms | 27544 KB | Output is correct |
28 | Correct | 140 ms | 27892 KB | Output is correct |
29 | Correct | 209 ms | 29136 KB | Output is correct |
30 | Correct | 105 ms | 24056 KB | Output is correct |
31 | Correct | 82 ms | 23408 KB | Output is correct |
32 | Correct | 106 ms | 24040 KB | Output is correct |
33 | Correct | 101 ms | 23116 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11604 KB | Output is correct |
2 | Correct | 6 ms | 11604 KB | Output is correct |
3 | Correct | 6 ms | 11544 KB | Output is correct |
4 | Correct | 16 ms | 11732 KB | Output is correct |
5 | Correct | 27 ms | 12160 KB | Output is correct |
6 | Correct | 8 ms | 11672 KB | Output is correct |
7 | Correct | 8 ms | 11604 KB | Output is correct |
8 | Correct | 11 ms | 11824 KB | Output is correct |
9 | Correct | 199 ms | 17348 KB | Output is correct |
10 | Correct | 234 ms | 28920 KB | Output is correct |
11 | Correct | 12 ms | 11732 KB | Output is correct |
12 | Correct | 98 ms | 12760 KB | Output is correct |
13 | Correct | 368 ms | 86840 KB | Output is correct |
14 | Correct | 596 ms | 114524 KB | Output is correct |
15 | Execution timed out | 5100 ms | 923844 KB | Time limit exceeded |
16 | Halted | 0 ms | 0 KB | - |