제출 #643367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643367		Pajaraja	Jail (JOI22_jail)	C++17	0 / 100	63 ms	110796 KiB

jail

#include <bits/stdc++.h>
#define MAXN 120007
#define MAXL 19
using namespace std;
vector<int> g[MAXN],v[2*MAXL*MAXN];
int p[MAXL][MAXN],ind[2][MAXL][MAXN],in[MAXN],out[MAXN],t,deg[MAXN];
void dfs(int s,int f)
{
    p[0][s]=f;
    in[s]=++t;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
    out[s]=t;
}
bool insub(int uu,int vv) {return in[uu]<=in[vv] && out[uu]>=out[vv];} //Jel v insub u
int oneunder(int uu,int vv)
{
    for(int i=MAXL-1;i>=0;i--) if(!insub(p[i][uu],vv)) uu=p[i][uu];
    return uu;
}
int lca(int uu,int vv)
{
    if(insub(uu,vv)) return uu;
    if(insub(vv,uu)) return vv;
    return p[0][oneunder(uu,vv)];
}
void dostuff(int uu,int vv,int type,int br)
{
    for(int i=MAXL-1;i>=0;i--) if(!insub(p[i][uu],vv))
    {
        if(type==0) v[br].push_back(ind[0][i][uu]);
        else v[ind[1][i][uu]].push_back(br);
        uu=p[i][uu];
    }
    if(type==0) v[br].push_back(ind[0][0][vv]);
    else v[ind[1][0][vv]].push_back(br);
}
int main()
{
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int n,m;
        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {
            int t1,t2;
            scanf("%d %d",&t1,&t2);
            g[t1].push_back(t2);
            g[t2].push_back(t1);
        }
        dfs(1,1); t=0;
        int c=2*n,br=0;
        for(int i=1;i<=n;i++) ind[0][0][i]=i;
        for(int i=1;i<=n;i++) ind[1][0][i]=n+i;
        for(int j=1;j<MAXL;j++) for(int i=1;i<=n;i++)
        {
            p[j][i]=p[j-1][p[j-1][i]];
            c++;
            ind[0][j][i]=c;
            v[c].push_back(ind[0][j-1][i]);
            v[c].push_back(ind[0][j-1][p[j-1][i]]);
            c++;
            ind[1][j][i]=c;
            v[ind[1][j-1][i]].push_back(c);
            v[ind[1][j-1][p[j-1][i]]].push_back(c);
        }
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            c++;
            int s,e;
            scanf("%d%d",&s,&e);
            v[s].push_back(c);
            v[c].push_back(n+e);
            int lc=lca(s,e);
            if(lc!=s && lc!=e)
            {
                dostuff(p[0][s],lc,0,c);
                dostuff(e,oneunder(e,lc),0,c);
                dostuff(p[0][e],lc,1,c);
                dostuff(s,oneunder(s,lc),1,c);
            }
            if(lc==s)
            {
                dostuff(e,oneunder(e,s),0,c);
                dostuff(p[0][e],s,1,c);
            }
            if(lc==e)
            {
                dostuff(s,oneunder(s,e),1,c);
                dostuff(p[0][s],e,0,c);
            }
        }
        queue<int> q;
        for(int i=1;i<=c;i++) deg[i]=0;
        for(int i=1;i<=c;i++) for(int j=0;j<v[i].size();j++) deg[v[i][j]]++;
        for(int i=1;i<=c;i++) if(deg[i]==0) q.push(i);
        //for(int i=1;i<=c;i++) for(int j=0;j<v[i].size();j++) printf("%d %d\n",i,v[i][j]);
        while(!q.empty())
        {
            br++;
            int s=q.front(); q.pop();
            for(int i=0;i<v[s].size();i++) {deg[v[s][i]]--; if(deg[v[s][i]]==0) q.push(v[s][i]);}
        }
        //printf("%d %d\n",c,br);
        if(br==c) printf("Yes\n");
        else printf("No\n");
        for(int i=1;i<=c;i++) v[i].clear();
        for(int i=1;i<=n;i++) g[i].clear();
    }
}

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

jail.cpp: In function 'void dfs(int, int)':
jail.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
      |                 ~^~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:97:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int i=1;i<=c;i++) for(int j=0;j<v[i].size();j++) deg[v[i][j]]++;
      |                                           ~^~~~~~~~~~~~
jail.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int i=0;i<v[s].size();i++) {deg[v[s][i]]--; if(deg[v[s][i]]==0) q.push(v[s][i]);}
      |                         ~^~~~~~~~~~~~
jail.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
jail.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
jail.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |             scanf("%d %d",&t1,&t2);
      |             ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
jail.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |             scanf("%d%d",&s,&e);
      |             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23