제출 #894954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894954		alexander707070	Jail (JOI22_jail)	C++14	100 / 100	1241 ms	236816 KiB

jail

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23