제출 #584607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584607		TimDee	슈퍼트리 잇기 (IOI20_supertrees)	C++14	0 / 100	1087 ms	22112 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
#define all(a) a.begin(), a.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define pi pair<int,int>
#define f first
#define s second

int mirror(vector<vector<int>>&a) {
  int n=a.size();
  for (int i=0; i<n; ++i) {
    for (int j=i+1; j<n; ++j) {
      if (a[i][j]!=a[j][i]) return 0;
      if (a[i][j]==3) return 0;
    }
  }
  forn(i,n) if (a[i][i]!=1) return 0;
  return 1;
}

int check(vector<vector<int>>&p,vector<int>&one,vector<int>&vis) {
  if (one.size()<=0) return 1;

  queue<int> q;
  forn(i,one.size()) {
    q.push(one[i]);
  }
  //forn(i,p.size()) cout<<vis[i]<<' '; cout<<'\n';
  while (!q.empty()) {
    int v=q.front(); q.pop();
    //cout<<"q "<<v<<'\n';
    forn(i,p.size()) {
      if (i==v) continue;
      if (p[v][i]==1 && vis[i]!=10) return 0;
    }
  }
  forn(i,one.size()) vis[one[i]]=1;
  return 1;
}

void colordfs(vector<int>&dp, vector<int>&vis, vector<vector<int>>&a, int v, int esk) {
  if (v==esk) return;
  if (vis[v]==2) return;
  vis[v]=2;
  dp[v]=2;
  forn(i,dp.size()) if (a[v][i]) colordfs(dp,vis,a,i,esk);
}

void dfs(vector<int>&dp, vector<int>&vis, vector<vector<int>>&a, int v, int last) {
  //cout<<v<<'\n';
  if (vis[v]==1) {
    //dp[v]++;
    colordfs(dp,vis,a,last,v);
    return;
  } else if (vis[v]==2) {
    return;
  }
  vis[v]=1;
  dp[v]=1;
  forn(i,a.size()) if (i!=last && a[v][i]) dfs(dp,vis,a,i,v);
}

int pathverif(vector<vector<int>>&a, vector<vector<int>>&p) {
  int n=a.size();
  forn(i,n) {
    vector<int> dp(n,0);
    vector<int> vis(n,0);
    dfs(dp,vis,a,i,-1);
    //forn(j,n) cout<<dp[j]<<' '; cout<<'\n';
    dp[i]=1;
    forn(j,n) if (dp[j]!=p[i][j]) return 0;
  }
  return 1;
}

int bfs(vector<vector<int>>&p, vector<int>&vis, int v, vector<pair<int,int>>&edges) {

  vector<int> one, two;
  vector<int> cycle;

  int n=p.size();

  forn(i,n) {
    if (i==v) continue;
    if (p[v][i]==1) one.pb(i);
    else if (p[v][i]==2) two.pb(i);
  }

  forn(i,one.size()) vis[one[i]]=10;
  forn(i,two.size()) vis[two[i]]=10;
  vis[v]=10;

  forn(i,one.size()) {
    forn(j,one.size()) {
      if (i==j) continue;
      if (p[one[i]][one[j]]!=1) return 0;
    }
  }
  forn(i,one.size()) edges.pb(mp(v,one[i]));

  //forn(i,one.size()) vis[one[i]]=1;
  //forn(i,two.size()) vis[two[i]]=1;
  //vis[v]=1;
 
  if (!two.size()) {
    //forn(i,one.size()) vis[one[i]]=1;
    //vis[v]=1;
    return check(p,one,vis);
  } else if (two.size()==1) return 0;
  else {
    forn(i,one.size()) {
      forn(j,two.size()) {
        if (p[one[i]][two[j]]!=2) return 0;
      }
    }
    cycle={v};
    forn(i,two.size()) {
      int foo=1;
      forn(j,cycle.size()) {
        if (p[two[i]][cycle[j]]==2) continue;
        else {foo=0; break;}
      }
      if (foo) cycle.pb(two[i]);
    }
  }

  queue<int> q;
  forn(i,cycle.size()) {
    if (cycle[i]!=v) q.push(cycle[i]);
  }

  while (!q.empty()) {
 
    int v=q.front(); q.pop();
    
    vector<int> one, two;

    forn(i,n) {
      if (i==v) continue;
      if (p[v][i]==1) one.pb(i);
      else if (p[v][i]==2) two.pb(i);
    }

    forn(i,one.size()) {
      forn(j,one.size()) {
        if (i==j) continue;
        if (p[one[i]][one[j]]!=1) return 0;
      }
    }
    forn(i,one.size()) edges.pb(mp(v,one[i]));

    forn(i,one.size()) if (vis[one[i]]!=10) return 0;
    forn(i,two.size()) if (vis[two[i]]!=10) return 0;
    if (vis[v]!=10) return 0;
 
    if (!two.size()) {
      continue;
    } else if (two.size()==1) return 0;
    else {
      forn(i,one.size()) {
        forn(j,two.size()) {
          if (p[one[i]][two[j]]!=2) return 0;
        }
      }
    }
  
  }

  if (cycle.size()<=2) return 0;

  forn(i,cycle.size()) {
    edges.pb(mp(cycle[i],cycle[(i+1)%cycle.size()]));
  }

  forn(i,one.size()) vis[one[i]]=1;
  forn(i,two.size()) vis[two[i]]=1;
  vis[v]=1;

  return 1;

}

int construct(std::vector<std::vector<int>> p) {
  int n = p.size();
  
  vector<vector<int>> a(n); 
  forn(i,n) a[i].assign(n,0);
 
  if (!mirror(p)) return 0;
 
  queue<int> q;
  q.push(0);
 
  vector<pair<int,int>> edges;
  vector<int> vis(n,0);
 
  forn(i,n) {
    if (vis[i]) continue;
    int x=bfs(p,vis,i,edges);
    if (x==0) return 0;
  }
 
  for (auto E:edges) {
    int u=E.f, v=E.s;
    a[u][v]=1;
    a[v][u]=1;
  }

  if (!pathverif(a,p)) return 0;
 
  build(a);
  return 1;
}

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

supertrees.cpp: In function 'int check(std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   28 |   forn(i,one.size()) {
      |        ~~~~~~~~~~~~               
supertrees.cpp:28:3: note: in expansion of macro 'forn'
   28 |   forn(i,one.size()) {
      |   ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   35 |     forn(i,p.size()) {
      |          ~~~~~~~~~~               
supertrees.cpp:35:5: note: in expansion of macro 'forn'
   35 |     forn(i,p.size()) {
      |     ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   40 |   forn(i,one.size()) vis[one[i]]=1;
      |        ~~~~~~~~~~~~               
supertrees.cpp:40:3: note: in expansion of macro 'forn'
   40 |   forn(i,one.size()) vis[one[i]]=1;
      |   ^~~~
supertrees.cpp: In function 'void colordfs(std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, int, int)':
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   49 |   forn(i,dp.size()) if (a[v][i]) colordfs(dp,vis,a,i,esk);
      |        ~~~~~~~~~~~                
supertrees.cpp:49:3: note: in expansion of macro 'forn'
   49 |   forn(i,dp.size()) if (a[v][i]) colordfs(dp,vis,a,i,esk);
      |   ^~~~
supertrees.cpp: In function 'void dfs(std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, int, int)':
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   63 |   forn(i,a.size()) if (i!=last && a[v][i]) dfs(dp,vis,a,i,v);
      |        ~~~~~~~~~~                 
supertrees.cpp:63:3: note: in expansion of macro 'forn'
   63 |   forn(i,a.size()) if (i!=last && a[v][i]) dfs(dp,vis,a,i,v);
      |   ^~~~
supertrees.cpp: In function 'int bfs(std::vector<std::vector<int> >&, std::vector<int>&, int, std::vector<std::pair<int, int> >&)':
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   92 |   forn(i,one.size()) vis[one[i]]=10;
      |        ~~~~~~~~~~~~               
supertrees.cpp:92:3: note: in expansion of macro 'forn'
   92 |   forn(i,one.size()) vis[one[i]]=10;
      |   ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   93 |   forn(i,two.size()) vis[two[i]]=10;
      |        ~~~~~~~~~~~~               
supertrees.cpp:93:3: note: in expansion of macro 'forn'
   93 |   forn(i,two.size()) vis[two[i]]=10;
      |   ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   96 |   forn(i,one.size()) {
      |        ~~~~~~~~~~~~               
supertrees.cpp:96:3: note: in expansion of macro 'forn'
   96 |   forn(i,one.size()) {
      |   ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
   97 |     forn(j,one.size()) {
      |          ~~~~~~~~~~~~             
supertrees.cpp:97:5: note: in expansion of macro 'forn'
   97 |     forn(j,one.size()) {
      |     ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  102 |   forn(i,one.size()) edges.pb(mp(v,one[i]));
      |        ~~~~~~~~~~~~               
supertrees.cpp:102:3: note: in expansion of macro 'forn'
  102 |   forn(i,one.size()) edges.pb(mp(v,one[i]));
      |   ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  114 |     forn(i,one.size()) {
      |          ~~~~~~~~~~~~             
supertrees.cpp:114:5: note: in expansion of macro 'forn'
  114 |     forn(i,one.size()) {
      |     ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  115 |       forn(j,two.size()) {
      |            ~~~~~~~~~~~~           
supertrees.cpp:115:7: note: in expansion of macro 'forn'
  115 |       forn(j,two.size()) {
      |       ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  120 |     forn(i,two.size()) {
      |          ~~~~~~~~~~~~             
supertrees.cpp:120:5: note: in expansion of macro 'forn'
  120 |     forn(i,two.size()) {
      |     ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  122 |       forn(j,cycle.size()) {
      |            ~~~~~~~~~~~~~~         
supertrees.cpp:122:7: note: in expansion of macro 'forn'
  122 |       forn(j,cycle.size()) {
      |       ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  131 |   forn(i,cycle.size()) {
      |        ~~~~~~~~~~~~~~             
supertrees.cpp:131:3: note: in expansion of macro 'forn'
  131 |   forn(i,cycle.size()) {
      |   ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  147 |     forn(i,one.size()) {
      |          ~~~~~~~~~~~~             
supertrees.cpp:147:5: note: in expansion of macro 'forn'
  147 |     forn(i,one.size()) {
      |     ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  148 |       forn(j,one.size()) {
      |            ~~~~~~~~~~~~           
supertrees.cpp:148:7: note: in expansion of macro 'forn'
  148 |       forn(j,one.size()) {
      |       ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  153 |     forn(i,one.size()) edges.pb(mp(v,one[i]));
      |          ~~~~~~~~~~~~             
supertrees.cpp:153:5: note: in expansion of macro 'forn'
  153 |     forn(i,one.size()) edges.pb(mp(v,one[i]));
      |     ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  155 |     forn(i,one.size()) if (vis[one[i]]!=10) return 0;
      |          ~~~~~~~~~~~~             
supertrees.cpp:155:5: note: in expansion of macro 'forn'
  155 |     forn(i,one.size()) if (vis[one[i]]!=10) return 0;
      |     ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  156 |     forn(i,two.size()) if (vis[two[i]]!=10) return 0;
      |          ~~~~~~~~~~~~             
supertrees.cpp:156:5: note: in expansion of macro 'forn'
  156 |     forn(i,two.size()) if (vis[two[i]]!=10) return 0;
      |     ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  163 |       forn(i,one.size()) {
      |            ~~~~~~~~~~~~           
supertrees.cpp:163:7: note: in expansion of macro 'forn'
  163 |       forn(i,one.size()) {
      |       ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  164 |         forn(j,two.size()) {
      |              ~~~~~~~~~~~~         
supertrees.cpp:164:9: note: in expansion of macro 'forn'
  164 |         forn(j,two.size()) {
      |         ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  174 |   forn(i,cycle.size()) {
      |        ~~~~~~~~~~~~~~             
supertrees.cpp:174:3: note: in expansion of macro 'forn'
  174 |   forn(i,cycle.size()) {
      |   ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  178 |   forn(i,one.size()) vis[one[i]]=1;
      |        ~~~~~~~~~~~~               
supertrees.cpp:178:3: note: in expansion of macro 'forn'
  178 |   forn(i,one.size()) vis[one[i]]=1;
      |   ^~~~
supertrees.cpp:4:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for (int i=0; i<n; ++i)
......
  179 |   forn(i,two.size()) vis[two[i]]=1;
      |        ~~~~~~~~~~~~               
supertrees.cpp:179:3: note: in expansion of macro 'forn'
  179 |   forn(i,two.size()) vis[two[i]]=1;
      |   ^~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4