oj.uz

답안 #567188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567188 2022-05-23T08:59:35 Z tqbfjotld Jail (JOI22_jail) C++14
0 / 100
 27 ms 19672 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adjl[120005];
int vis[400005];
int cur;
int fs[120005];
int ls[120005];

int A[120005];
int B[120005];

vector<int> adjl2[400005];
int curid = 0;

struct node{
    int s,e,inid,outid;
    node *l,*r;
    vector<int> stuff;
    node (int _s, int _e){
        s = _s; e = _e;
        inid = curid++;
        outid = curid++;
        if (s!=e){
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
        }
    }
    void add(int a, int b, int val){
        if (a<=s && e<=b){
            stuff.push_back(val);
            return;
        }
        if (b<=(s+e)/2) l->add(a,b,val);
        else if (a>(s+e)/2) r->add(a,b,val);
        else {
            l->add(a,b,val);
            r->add(a,b,val);
        }
    }
    void constructstuff(){
        if (s!=e){
            l->constructstuff();
            r->constructstuff();
        }
        for (auto y : stuff){
            adjl2[inid].push_back(y);
            adjl2[y].push_back(outid);
        }
    }
    void constructbef(int pos, int val){
        adjl2[val].push_back(inid);
        if (s==e) return;
        if (pos<=(s+e)/2) l->constructbef(pos,val);
        else r->constructbef(pos,val);
    }
    void constructaft(int pos, int val){
        adjl2[outid].push_back(val);
        if (s==e) return;
        if (pos<=(s+e)/2) l->constructaft(pos,val);
        else r->constructaft(pos,val);
    }

}*root;


int p[120005];
int hd[120005];
int dep[120005];
int sz[120005];
int pre[120005];
int ct = 0;

void dfs(int nd){
    sz[nd] = 1;
    for (auto x : adjl[nd]){
        if (x==p[nd]){
            continue;
        }
        dep[x] = dep[nd]+1;
        p[x] = nd;
        dfs(x);
        sz[nd] += sz[x];
    }
}

void decomp(int nd, int head){
    hd[nd] = head;
    pre[nd] = ct++;
    int mx = 0;
    int mnd = -1;
    for (auto x : adjl[nd]){
        if (x==p[nd]) continue;
        if (sz[x]>mx){
            mx = sz[x];
            mnd = x;
        }
    }
    if (mnd==-1) return;
    decomp(mnd,head);
    for (auto x : adjl[nd]){
        if (x==p[nd]||x==mnd) continue;
        decomp(x,x);
    }
}


bool checkcycle(int nd){
    if (vis[nd]==2) return false;
    vis[nd] = 1;
    for (auto x : adjl2[nd]){
        if (vis[x]==1) return true;
        if (checkcycle(x)) return true;
    }
    vis[nd] = 2;
    return false;
}

int p2[120005][20];

int anc(int a, int amt){
    for (int x = 0; x<20; x++){
        if ((1<<x)&amt){
            a = p2[a][x];
        }
    }
    return a;
}

int main(){
    int Q;
    scanf("%d",&Q);
    while (Q--){
        int n;
        scanf("%d",&n);
        ct = 0;
        for (int x = 1; x<=n; x++){
            adjl[x].clear();
        }
        for (int x = 0; x<n-1; x++){
            int a,b;
            scanf("%d%d",&a,&b);
            adjl[a].push_back(b);
            adjl[b].push_back(a);
        }
        p[1] = 0;
        dfs(1);
        decomp(1,1);

        for (int x = 0; x<=n; x++){
            p2[x][0] = p[x];
        }
        for (int x = 1; x<20; x++){
            for (int y = 0; y<=n; y++){
                p2[y][x] = p2[p2[y][x-1]][x-1];
            }
        }

        int m;
        scanf("%d",&m);
        curid = m;
        for (int x = 1; x<=n; x++){
            fs[x] = -1;
            ls[x] = -1;
        }
        for (int x = 0; x<m; x++){
            scanf("%d%d",&A[x],&B[x]);
            fs[A[x]] = x;
            ls[B[x]] = x;
        }
        root = new node(0,n-1);
        for (int x = 0; x<m; x++){
            int a = A[x];
            int b = B[x];
            if (dep[a]>dep[b]) swap(a,b);
            if (p[b]==a) continue;
            if (anc(b,dep[b]-dep[a])==a){
                a = anc(b,dep[b]-dep[a]-1);
                b = p[b];
            }
            else{
                a = p[a];
                b = p[b];
            }
            while (hd[a]!=hd[b]){
                if (dep[hd[a]]<dep[hd[b]]) swap(a,b);
                root->add(pre[hd[a]],pre[a],x);
                a = p[hd[a]];
            }
            if (pre[a]>pre[b])swap(a,b);
            root->add(pre[a],pre[b],x);
        }
        for (int x = 0; x<3*n+5; x++){
            adjl2[x].clear();
            vis[x] = 0;
        }
        root->constructstuff();
        for (int x = 1; x<=n; x++){
            if (fs[x]!=-1 && ls[x]!=-1) adjl2[fs[x]].push_back(ls[x]);
            if (fs[x]!=-1){
                root->constructbef(pre[x],fs[x]);
            }
            if (ls[x]!=-1){
                root->constructaft(pre[x],ls[x]);
            }
        }
        bool ans = true;
        for (int x = 0; x<curid; x++){
            if (checkcycle(x)){
                ans = false;
            }
        }
        printf(ans?"Yes\n":"No\n");
    }
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
jail.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
jail.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
jail.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
jail.cpp:167:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |             scanf("%d%d",&A[x],&B[x]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 26 ms 19672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Incorrect 8 ms 13140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Incorrect 8 ms 13140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Incorrect 8 ms 13140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Incorrect 8 ms 13140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12576 KB Output is correct
3 Correct 7 ms 12500 KB Output is correct
4 Correct 7 ms 12500 KB Output is correct
5 Incorrect 27 ms 15404 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 26 ms 19672 KB Output isn't correct
5 Halted 0 ms 0 KB -