oj.uz

답안 #894954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894954 2023-12-29T09:43:07 Z alexander707070 Jail (JOI22_jail) C++14
100 / 100
 1241 ms 236816 KB 
#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n,m,q,a,b,k;
int s[MAXN],t[MAXN],tt,parent[MAXN],comp[10*MAXN];
int sz[MAXN],pos[MAXN],head[MAXN],heavy[MAXN],ret[MAXN],dep[MAXN];
int start[MAXN],fin[MAXN],vis[10*MAXN];
bool dali;

vector<int> v[MAXN],g[10*MAXN],r[10*MAXN];
stack<int> st;

void reset(){
    tt=k=0;
    for(int i=1;i<=n;i++){
        start[i]=fin[i]=0;
        v[i].clear(); sz[i]=0;
    }
    for(int i=1;i<=10*n;i++){
        g[i].clear(); r[i].clear(); 
        vis[i]=0;
    }
    dali=false;
}

void dfs(int x,int p,int d){
    sz[x]=1; dep[x]=d; parent[x]=p;

    heavy[x]=0;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x,d+1);
        if(sz[v[x][i]]>sz[heavy[x]])heavy[x]=v[x][i];

        sz[x]+=sz[v[x][i]];
    }
}

void decompose(int x,int p,int h){
    tt++; pos[x]=tt; ret[tt]=x; head[x]=h;

    if(heavy[x]!=0)decompose(heavy[x],x,h);

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p or v[x][i]==heavy[x])continue;
        decompose(v[x][i],x,v[x][i]);
    }
}

void add_edge(int from,int to){
    g[from].push_back(to);
    r[to].push_back(from);
}

void build(int v,int l,int r){
    if(l==r){
        if(fin[ret[l]]!=0)add_edge(v+n,fin[ret[l]]);
        if(start[ret[l]]!=0)add_edge(start[ret[l]],v+5*n);
    }else{
        int tt=(l+r)/2;
        build(2*v,l,tt);
        build(2*v+1,tt+1,r);

        add_edge(v+n,2*v+n);
        add_edge(v+n,2*v+1+n);

        add_edge(2*v+5*n,v+5*n);
        add_edge(2*v+1+5*n,v+5*n);
    }
}

void connect(int v,int l,int r,int ll,int rr,int root){
    if(ll>rr)return;
    if(l==ll and r==rr){
        add_edge(root,v+n);
        add_edge(v+5*n,root);
    }else{
        int tt=(l+r)/2;
        connect(2*v,l,tt,ll,min(tt,rr),root);
        connect(2*v+1,tt+1,r,max(tt+1,ll),rr,root);
    }
}

void query(int x,int y,int root){

    while(head[x]!=head[y]){
        if(dep[head[x]]<dep[head[y]])swap(x,y);
        connect(1,1,n,pos[head[x]],pos[x],root);
        x=parent[head[x]];
    }
    if(pos[x]>pos[y])swap(x,y);

    connect(1,1,n,pos[x],pos[y],root);
}

void topsort(int x){
    vis[x]=1;
    for(int i=0;i<g[x].size();i++){
        if(vis[g[x][i]]==0)topsort(g[x][i]);
    }
    st.push(x);
}

void scc(int x){
    vis[x]=2;
    comp[x]=k;

    for(int i=0;i<r[x].size();i++){
        if(vis[r[x][i]]==1)scc(r[x][i]);
    }
}

void solve(){

    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>s[i]>>t[i];
        start[s[i]]=i;
        fin[t[i]]=i;
    }


    dfs(1,0,0);
    decompose(1,0,1);
    build(1,1,n);

    for(int i=1;i<=m;i++){
        query(s[i],t[i],i);
    }

    for(int i=1;i<=10*n;i++){
        if(vis[i]==1)continue;
        topsort(i);
    }

    while(!st.empty()){
        if(vis[st.top()]==1){
            k++; scc(st.top());
        }
        st.pop();
    }

    sort(comp+1,comp+m+1);
    for(int i=2;i<=m;i++){
        if(comp[i]==comp[i-1])dali=true;
    }

    if(dali)cout<<"No\n";
    else cout<<"Yes\n";

    reset();
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>q;
    while(q>0){
        reset();
        solve();
        q--;
    }

    return 0;
}

Compilation message

jail.cpp: In function 'void dfs(int, int, int)':
jail.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
jail.cpp: In function 'void decompose(int, int, int)':
jail.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
jail.cpp: In function 'void topsort(int)':
jail.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~
jail.cpp: In function 'void scc(int)':
jail.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i=0;i<r[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 109148 KB Output is correct
2 Correct 23 ms 109148 KB Output is correct
3 Correct 23 ms 109148 KB Output is correct
4 Correct 38 ms 109404 KB Output is correct
5 Correct 54 ms 109304 KB Output is correct
6 Correct 27 ms 109404 KB Output is correct
7 Correct 25 ms 109400 KB Output is correct
8 Correct 25 ms 109404 KB Output is correct
9 Correct 73 ms 111956 KB Output is correct
10 Correct 171 ms 159312 KB Output is correct
11 Correct 31 ms 109400 KB Output is correct
12 Correct 74 ms 109404 KB Output is correct
13 Correct 256 ms 174372 KB Output is correct
14 Correct 278 ms 176804 KB Output is correct
15 Correct 530 ms 186668 KB Output is correct
16 Correct 964 ms 227900 KB Output is correct
17 Correct 363 ms 193284 KB Output is correct
18 Correct 269 ms 179540 KB Output is correct
19 Correct 342 ms 189520 KB Output is correct
20 Correct 373 ms 189508 KB Output is correct
21 Correct 389 ms 191828 KB Output is correct
22 Correct 234 ms 170848 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 109404 KB Output is correct
2 Correct 23 ms 109400 KB Output is correct
3 Correct 24 ms 109404 KB Output is correct
4 Correct 24 ms 109264 KB Output is correct
5 Correct 24 ms 109404 KB Output is correct
6 Correct 28 ms 109304 KB Output is correct
7 Correct 25 ms 109656 KB Output is correct
8 Correct 24 ms 109404 KB Output is correct
9 Correct 24 ms 109288 KB Output is correct
10 Correct 26 ms 109400 KB Output is correct
11 Correct 24 ms 109404 KB Output is correct
12 Correct 24 ms 109404 KB Output is correct
13 Correct 23 ms 109400 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 109404 KB Output is correct
2 Correct 23 ms 109400 KB Output is correct
3 Correct 24 ms 109404 KB Output is correct
4 Correct 24 ms 109264 KB Output is correct
5 Correct 24 ms 109404 KB Output is correct
6 Correct 28 ms 109304 KB Output is correct
7 Correct 25 ms 109656 KB Output is correct
8 Correct 24 ms 109404 KB Output is correct
9 Correct 24 ms 109288 KB Output is correct
10 Correct 26 ms 109400 KB Output is correct
11 Correct 24 ms 109404 KB Output is correct
12 Correct 24 ms 109404 KB Output is correct
13 Correct 23 ms 109400 KB Output is correct
14 Correct 23 ms 109144 KB Output is correct
15 Correct 25 ms 109148 KB Output is correct
16 Correct 26 ms 109624 KB Output is correct
17 Correct 26 ms 109292 KB Output is correct
18 Correct 24 ms 109404 KB Output is correct
19 Correct 25 ms 109400 KB Output is correct
20 Correct 24 ms 109404 KB Output is correct
21 Correct 24 ms 109476 KB Output is correct
22 Correct 25 ms 109404 KB Output is correct
23 Correct 24 ms 109148 KB Output is correct
24 Correct 23 ms 109328 KB Output is correct
25 Correct 25 ms 109400 KB Output is correct
26 Correct 23 ms 109320 KB Output is correct
27 Correct 25 ms 109404 KB Output is correct
28 Correct 23 ms 109148 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 109404 KB Output is correct
2 Correct 23 ms 109400 KB Output is correct
3 Correct 24 ms 109404 KB Output is correct
4 Correct 24 ms 109264 KB Output is correct
5 Correct 24 ms 109404 KB Output is correct
6 Correct 28 ms 109304 KB Output is correct
7 Correct 25 ms 109656 KB Output is correct
8 Correct 24 ms 109404 KB Output is correct
9 Correct 24 ms 109288 KB Output is correct
10 Correct 26 ms 109400 KB Output is correct
11 Correct 24 ms 109404 KB Output is correct
12 Correct 24 ms 109404 KB Output is correct
13 Correct 23 ms 109400 KB Output is correct
14 Correct 23 ms 109144 KB Output is correct
15 Correct 25 ms 109148 KB Output is correct
16 Correct 26 ms 109624 KB Output is correct
17 Correct 26 ms 109292 KB Output is correct
18 Correct 24 ms 109404 KB Output is correct
19 Correct 25 ms 109400 KB Output is correct
20 Correct 24 ms 109404 KB Output is correct
21 Correct 24 ms 109476 KB Output is correct
22 Correct 25 ms 109404 KB Output is correct
23 Correct 24 ms 109148 KB Output is correct
24 Correct 23 ms 109328 KB Output is correct
25 Correct 25 ms 109400 KB Output is correct
26 Correct 23 ms 109320 KB Output is correct
27 Correct 25 ms 109404 KB Output is correct
28 Correct 23 ms 109148 KB Output is correct
29 Correct 26 ms 109520 KB Output is correct
30 Correct 25 ms 109404 KB Output is correct
31 Correct 26 ms 109404 KB Output is correct
32 Correct 28 ms 109408 KB Output is correct
33 Correct 25 ms 109404 KB Output is correct
34 Correct 27 ms 109404 KB Output is correct
35 Correct 26 ms 109404 KB Output is correct
36 Correct 25 ms 109532 KB Output is correct
37 Correct 27 ms 109532 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 109404 KB Output is correct
2 Correct 23 ms 109400 KB Output is correct
3 Correct 24 ms 109404 KB Output is correct
4 Correct 24 ms 109264 KB Output is correct
5 Correct 24 ms 109404 KB Output is correct
6 Correct 28 ms 109304 KB Output is correct
7 Correct 25 ms 109656 KB Output is correct
8 Correct 24 ms 109404 KB Output is correct
9 Correct 24 ms 109288 KB Output is correct
10 Correct 26 ms 109400 KB Output is correct
11 Correct 24 ms 109404 KB Output is correct
12 Correct 24 ms 109404 KB Output is correct
13 Correct 23 ms 109400 KB Output is correct
14 Correct 23 ms 109144 KB Output is correct
15 Correct 25 ms 109148 KB Output is correct
16 Correct 26 ms 109624 KB Output is correct
17 Correct 26 ms 109292 KB Output is correct
18 Correct 24 ms 109404 KB Output is correct
19 Correct 25 ms 109400 KB Output is correct
20 Correct 24 ms 109404 KB Output is correct
21 Correct 24 ms 109476 KB Output is correct
22 Correct 25 ms 109404 KB Output is correct
23 Correct 24 ms 109148 KB Output is correct
24 Correct 23 ms 109328 KB Output is correct
25 Correct 25 ms 109400 KB Output is correct
26 Correct 23 ms 109320 KB Output is correct
27 Correct 25 ms 109404 KB Output is correct
28 Correct 23 ms 109148 KB Output is correct
29 Correct 26 ms 109520 KB Output is correct
30 Correct 25 ms 109404 KB Output is correct
31 Correct 26 ms 109404 KB Output is correct
32 Correct 28 ms 109408 KB Output is correct
33 Correct 25 ms 109404 KB Output is correct
34 Correct 27 ms 109404 KB Output is correct
35 Correct 26 ms 109404 KB Output is correct
36 Correct 25 ms 109532 KB Output is correct
37 Correct 27 ms 109532 KB Output is correct
38 Correct 73 ms 111952 KB Output is correct
39 Correct 166 ms 159312 KB Output is correct
40 Correct 87 ms 111920 KB Output is correct
41 Correct 90 ms 111956 KB Output is correct
42 Correct 73 ms 112208 KB Output is correct
43 Correct 63 ms 111452 KB Output is correct
44 Correct 39 ms 109964 KB Output is correct
45 Correct 196 ms 151576 KB Output is correct
46 Correct 177 ms 151584 KB Output is correct
47 Correct 171 ms 156144 KB Output is correct
48 Correct 173 ms 156404 KB Output is correct
49 Correct 168 ms 151988 KB Output is correct
50 Correct 170 ms 151888 KB Output is correct
51 Correct 169 ms 152912 KB Output is correct
52 Correct 159 ms 152816 KB Output is correct
53 Correct 45 ms 114516 KB Output is correct
54 Correct 177 ms 151636 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 109280 KB Output is correct
2 Correct 26 ms 109148 KB Output is correct
3 Correct 25 ms 109148 KB Output is correct
4 Correct 23 ms 109272 KB Output is correct
5 Correct 31 ms 109404 KB Output is correct
6 Correct 24 ms 109404 KB Output is correct
7 Correct 24 ms 109404 KB Output is correct
8 Correct 23 ms 109404 KB Output is correct
9 Correct 22 ms 109404 KB Output is correct
10 Correct 23 ms 109404 KB Output is correct
11 Correct 23 ms 109320 KB Output is correct
12 Correct 25 ms 109404 KB Output is correct
13 Correct 55 ms 109404 KB Output is correct
14 Correct 78 ms 109444 KB Output is correct
15 Correct 65 ms 109472 KB Output is correct
16 Correct 271 ms 155732 KB Output is correct
17 Correct 570 ms 181328 KB Output is correct
18 Correct 990 ms 215872 KB Output is correct
19 Correct 333 ms 161616 KB Output is correct
20 Correct 351 ms 161588 KB Output is correct
21 Correct 345 ms 161688 KB Output is correct
22 Correct 575 ms 178872 KB Output is correct
23 Correct 409 ms 178244 KB Output is correct
24 Correct 432 ms 178552 KB Output is correct
25 Correct 439 ms 178508 KB Output is correct
26 Correct 441 ms 178892 KB Output is correct
27 Correct 595 ms 174540 KB Output is correct
28 Correct 637 ms 183216 KB Output is correct
29 Correct 576 ms 176844 KB Output is correct
30 Correct 387 ms 170944 KB Output is correct
31 Correct 418 ms 172416 KB Output is correct
32 Correct 397 ms 168636 KB Output is correct
33 Correct 404 ms 172580 KB Output is correct

Subtask #7
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 109148 KB Output is correct
2 Correct 23 ms 109148 KB Output is correct
3 Correct 23 ms 109148 KB Output is correct
4 Correct 38 ms 109404 KB Output is correct
5 Correct 54 ms 109304 KB Output is correct
6 Correct 27 ms 109404 KB Output is correct
7 Correct 25 ms 109400 KB Output is correct
8 Correct 25 ms 109404 KB Output is correct
9 Correct 73 ms 111956 KB Output is correct
10 Correct 171 ms 159312 KB Output is correct
11 Correct 31 ms 109400 KB Output is correct
12 Correct 74 ms 109404 KB Output is correct
13 Correct 256 ms 174372 KB Output is correct
14 Correct 278 ms 176804 KB Output is correct
15 Correct 530 ms 186668 KB Output is correct
16 Correct 964 ms 227900 KB Output is correct
17 Correct 363 ms 193284 KB Output is correct
18 Correct 269 ms 179540 KB Output is correct
19 Correct 342 ms 189520 KB Output is correct
20 Correct 373 ms 189508 KB Output is correct
21 Correct 389 ms 191828 KB Output is correct
22 Correct 234 ms 170848 KB Output is correct
23 Correct 22 ms 109404 KB Output is correct
24 Correct 23 ms 109400 KB Output is correct
25 Correct 24 ms 109404 KB Output is correct
26 Correct 24 ms 109264 KB Output is correct
27 Correct 24 ms 109404 KB Output is correct
28 Correct 28 ms 109304 KB Output is correct
29 Correct 25 ms 109656 KB Output is correct
30 Correct 24 ms 109404 KB Output is correct
31 Correct 24 ms 109288 KB Output is correct
32 Correct 26 ms 109400 KB Output is correct
33 Correct 24 ms 109404 KB Output is correct
34 Correct 24 ms 109404 KB Output is correct
35 Correct 23 ms 109400 KB Output is correct
36 Correct 23 ms 109144 KB Output is correct
37 Correct 25 ms 109148 KB Output is correct
38 Correct 26 ms 109624 KB Output is correct
39 Correct 26 ms 109292 KB Output is correct
40 Correct 24 ms 109404 KB Output is correct
41 Correct 25 ms 109400 KB Output is correct
42 Correct 24 ms 109404 KB Output is correct
43 Correct 24 ms 109476 KB Output is correct
44 Correct 25 ms 109404 KB Output is correct
45 Correct 24 ms 109148 KB Output is correct
46 Correct 23 ms 109328 KB Output is correct
47 Correct 25 ms 109400 KB Output is correct
48 Correct 23 ms 109320 KB Output is correct
49 Correct 25 ms 109404 KB Output is correct
50 Correct 23 ms 109148 KB Output is correct
51 Correct 26 ms 109520 KB Output is correct
52 Correct 25 ms 109404 KB Output is correct
53 Correct 26 ms 109404 KB Output is correct
54 Correct 28 ms 109408 KB Output is correct
55 Correct 25 ms 109404 KB Output is correct
56 Correct 27 ms 109404 KB Output is correct
57 Correct 26 ms 109404 KB Output is correct
58 Correct 25 ms 109532 KB Output is correct
59 Correct 27 ms 109532 KB Output is correct
60 Correct 73 ms 111952 KB Output is correct
61 Correct 166 ms 159312 KB Output is correct
62 Correct 87 ms 111920 KB Output is correct
63 Correct 90 ms 111956 KB Output is correct
64 Correct 73 ms 112208 KB Output is correct
65 Correct 63 ms 111452 KB Output is correct
66 Correct 39 ms 109964 KB Output is correct
67 Correct 196 ms 151576 KB Output is correct
68 Correct 177 ms 151584 KB Output is correct
69 Correct 171 ms 156144 KB Output is correct
70 Correct 173 ms 156404 KB Output is correct
71 Correct 168 ms 151988 KB Output is correct
72 Correct 170 ms 151888 KB Output is correct
73 Correct 169 ms 152912 KB Output is correct
74 Correct 159 ms 152816 KB Output is correct
75 Correct 45 ms 114516 KB Output is correct
76 Correct 177 ms 151636 KB Output is correct
77 Correct 22 ms 109280 KB Output is correct
78 Correct 26 ms 109148 KB Output is correct
79 Correct 25 ms 109148 KB Output is correct
80 Correct 23 ms 109272 KB Output is correct
81 Correct 31 ms 109404 KB Output is correct
82 Correct 24 ms 109404 KB Output is correct
83 Correct 24 ms 109404 KB Output is correct
84 Correct 23 ms 109404 KB Output is correct
85 Correct 22 ms 109404 KB Output is correct
86 Correct 23 ms 109404 KB Output is correct
87 Correct 23 ms 109320 KB Output is correct
88 Correct 25 ms 109404 KB Output is correct
89 Correct 55 ms 109404 KB Output is correct
90 Correct 78 ms 109444 KB Output is correct
91 Correct 65 ms 109472 KB Output is correct
92 Correct 271 ms 155732 KB Output is correct
93 Correct 570 ms 181328 KB Output is correct
94 Correct 990 ms 215872 KB Output is correct
95 Correct 333 ms 161616 KB Output is correct
96 Correct 351 ms 161588 KB Output is correct
97 Correct 345 ms 161688 KB Output is correct
98 Correct 575 ms 178872 KB Output is correct
99 Correct 409 ms 178244 KB Output is correct
100 Correct 432 ms 178552 KB Output is correct
101 Correct 439 ms 178508 KB Output is correct
102 Correct 441 ms 178892 KB Output is correct
103 Correct 595 ms 174540 KB Output is correct
104 Correct 637 ms 183216 KB Output is correct
105 Correct 576 ms 176844 KB Output is correct
106 Correct 387 ms 170944 KB Output is correct
107 Correct 418 ms 172416 KB Output is correct
108 Correct 397 ms 168636 KB Output is correct
109 Correct 404 ms 172580 KB Output is correct
110 Correct 76 ms 110412 KB Output is correct
111 Correct 57 ms 110104 KB Output is correct
112 Correct 603 ms 190232 KB Output is correct
113 Correct 313 ms 167760 KB Output is correct
114 Correct 472 ms 177808 KB Output is correct
115 Correct 181 ms 153588 KB Output is correct
116 Correct 393 ms 162128 KB Output is correct
117 Correct 1241 ms 236816 KB Output is correct
118 Correct 187 ms 153432 KB Output is correct
119 Correct 188 ms 153332 KB Output is correct
120 Correct 45 ms 115664 KB Output is correct
121 Correct 438 ms 169300 KB Output is correct
122 Correct 435 ms 169400 KB Output is correct
123 Correct 351 ms 171192 KB Output is correct
124 Correct 394 ms 171472 KB Output is correct
125 Correct 348 ms 172884 KB Output is correct
126 Correct 987 ms 227416 KB Output is correct
127 Correct 488 ms 197032 KB Output is correct
128 Correct 403 ms 199472 KB Output is correct
129 Correct 388 ms 197020 KB Output is correct
130 Correct 424 ms 198784 KB Output is correct