제출 #1084805

#제출 시각아이디문제언어결과실행 시간메모리
1084805DucNguyen2007Bitaro’s Party (JOI18_bitaro)C++14
컴파일 에러
0 ms0 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second const int maxN=1e5+5; const ll inf=2e18; int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1]; vector<int> adj[maxN+1],topo; vector<pii> vec[maxN+1]; bool vis[maxN+1]; void dfs(int u) { vis[u]=true; for(auto v:adj[u]) { if(!vis[v]) { dfs(v); } } topo.push_back(u); } void meg(int u,int v) { vector<pii> vt; int i=0,j=0; for(auto i:vec[u]) { vis[i.fi]=false; } for(auto i:vec[v]) { vis[i.fi]=false; } while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block) { while(i<vec[u].size()&&vis[vec[u][i].fi]) { i++; } while(j<vec[v].size()&&vis[vec[v][j].fi]) { j++; } if(i>=vec[u].size()||j>=vec[v].size()) { break; } int p1=vec[u][i].se,p2=vec[v][j].se; if(p1+1>p2) { vt.push_back({vec[u][i].fi,p1+1}); vis[vec[u][i].fi]=true; i++; } else { vt.push_back({vec[v][j].fi,p2}); vis[vec[v][j].fi]=true; j++; } } while(i<vec[u].size()&&vt.size()<block) { while(i<vec[u].size()&&vis[vec[u][i].fi]) { i++; } if(i>=vec[u].size()) { break; } vt.push_back({vec[u][i].fi,vec[u][i].se+1}); i++; } while(j<vec[v].size()&&vt.size()<block) { while(j<vec[v].size()&&vis[vec[v][j].fi]) { j++; } if(j>=vec[v].size()) { break; } vt.push_back({vec[v][j].fi,vec[v][j].se}); j++; } vec[v]=vt; } void make() { for(auto u:topo) { vec[u].push_back({u,0}); for(auto v:adj[u]) { //cout<<u<<" "<<v<<'\n'; meg(u,v); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; adj[u].push_back(v); } block=sqrt(n); for(int i=1;i<=n;i++) { if(!vis[i]) { dfs(i); } } memset(dp,0,sizeof(dp)); reverse(topo.begin(),topo.end()); make(); while(q--) { int t,y; cin>>t>>y; if(y>=block) { for(int i=1;i<=n;i++) { dp[i]=0; } } for(int i=1;i<=y;i++) { int u; cin>>u; a[i]=u; dp[u]=INT_MIN; if(y<block) { cnt[u]++; } } if(y>=block) { for(auto u:topo) { for(auto v:adj[u]) { dp[v]=max(dp[v],dp[u]+1); } } if(dp[t]<0) { cout<<-1; } else cout<<dp[t]; } else { int ans=-1; for(auto u:vec[t]) { if(!cnt[u.fi]) { ans=u.se; break; } } cout<<ans; } cout<<'\n'; for(int i=1;i<=y;i++) { cnt[a[i]]=0; } } } /*4 8 5 2 3 2 3 1 3 1 3 3 4 1 2 1 2 1 2 2 1 4 1 3 4 2 2 3 4 1 1 4 2 4 2 1 3 3 1 4*/ #include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second const int maxN=1e5+5; const ll inf=2e18; int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1]; vector<int> adj[maxN+1],topo; vector<pii> vec[maxN+1]; bool vis[maxN+1]; void dfs(int u) { vis[u]=true; for(auto v:adj[u]) { if(!vis[v]) { dfs(v); } } topo.push_back(u); } void meg(int u,int v) { vector<pii> vt; int i=0,j=0; for(auto i:vec[u]) { vis[i.fi]=false; } for(auto i:vec[v]) { vis[i.fi]=false; } while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block) { while(i<vec[u].size()&&vis[vec[u][i].fi]) { i++; } while(j<vec[v].size()&&vis[vec[v][j].fi]) { j++; } if(i>=vec[u].size()||j>=vec[v].size()) { break; } int p1=vec[u][i].se,p2=vec[v][j].se; if(p1+1>p2) { vt.push_back({vec[u][i].fi,p1+1}); vis[vec[u][i].fi]=true; i++; } else { vt.push_back({vec[v][j].fi,p2}); vis[vec[v][j].fi]=true; j++; } } while(i<vec[u].size()&&vt.size()<block) { while(i<vec[u].size()&&vis[vec[u][i].fi]) { i++; } if(i>=vec[u].size()) { break; } vt.push_back({vec[u][i].fi,vec[u][i].se+1}); i++; } while(j<vec[v].size()&&vt.size()<block) { while(j<vec[v].size()&&vis[vec[v][j].fi]) { j++; } if(j>=vec[v].size()) { break; } vt.push_back({vec[v][j].fi,vec[v][j].se}); j++; } vec[v]=vt; } void make() { for(auto u:topo) { vec[u].push_back({u,0}); for(auto v:adj[u]) { //cout<<u<<" "<<v<<'\n'; meg(u,v); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; adj[u].push_back(v); } block=sqrt(n); for(int i=1;i<=n;i++) { if(!vis[i]) { dfs(i); } } memset(dp,0,sizeof(dp)); reverse(topo.begin(),topo.end()); make(); while(q--) { int t,y; cin>>t>>y; if(y>=block) { for(int i=1;i<=n;i++) { dp[i]=0; } } for(int i=1;i<=y;i++) { int u; cin>>u; a[i]=u; dp[u]=INT_MIN; if(y<block) { cnt[u]++; } } if(y>=block) { for(auto u:topo) { for(auto v:adj[u]) { dp[v]=max(dp[v],dp[u]+1); } } if(dp[t]<0) { cout<<-1; } else cout<<dp[t]; } else { int ans=-1; for(auto u:vec[t]) { if(!cnt[u.fi]) { ans=u.se; break; } } cout<<ans; } cout<<'\n'; for(int i=1;i<=y;i++) { cnt[a[i]]=0; } } }

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

bitaro.cpp: In function 'void meg(int, int)':
bitaro.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:38:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                            ~^~~~~~~~~~~~~~
bitaro.cpp:38:54: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                                             ~~~~~~~~~^~~~~~
bitaro.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:48:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if(i>=vec[u].size()||j>=vec[v].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp:48:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if(i>=vec[u].size()||j>=vec[v].size())
      |                              ~^~~~~~~~~~~~~~~
bitaro.cpp:66:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     while(i<vec[u].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:66:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     while(i<vec[u].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:72:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(i>=vec[u].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp:79:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while(j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:79:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |     while(j<vec[v].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:85:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         if(j>=vec[v].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp: At global scope:
bitaro.cpp:207:11: error: redefinition of 'const int maxN'
  207 | const int maxN=1e5+5;
      |           ^~~~
bitaro.cpp:8:11: note: 'const int maxN' previously defined here
    8 | const int maxN=1e5+5;
      |           ^~~~
bitaro.cpp:208:10: error: redefinition of 'const long long int inf'
  208 | const ll inf=2e18;
      |          ^~~
bitaro.cpp:9:10: note: 'const long long int inf' previously defined here
    9 | const ll inf=2e18;
      |          ^~~
bitaro.cpp:209:5: error: redefinition of 'int n'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |     ^
bitaro.cpp:10:5: note: 'int n' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |     ^
bitaro.cpp:209:7: error: redefinition of 'int m'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |       ^
bitaro.cpp:10:7: note: 'int m' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |       ^
bitaro.cpp:209:9: error: redefinition of 'int q'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |         ^
bitaro.cpp:10:9: note: 'int q' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |         ^
bitaro.cpp:209:11: error: redefinition of 'int dp [100006]'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |           ^~
bitaro.cpp:10:11: note: 'int dp [100006]' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |           ^~
bitaro.cpp:209:22: error: redefinition of 'int block'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                      ^~~~~
bitaro.cpp:10:22: note: 'int block' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                      ^~~~~
bitaro.cpp:209:28: error: redefinition of 'int a [100006]'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                            ^
bitaro.cpp:10:28: note: 'int a [100006]' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                            ^
bitaro.cpp:209:38: error: redefinition of 'int cnt [100006]'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                                      ^~~
bitaro.cpp:10:38: note: 'int cnt [100006]' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                                      ^~~
bitaro.cpp:210:13: error: redefinition of 'std::vector<int> adj [100006]'
  210 | vector<int> adj[maxN+1],topo;
      |             ^~~
bitaro.cpp:11:13: note: 'std::vector<int> adj [100006]' previously declared here
   11 | vector<int> adj[maxN+1],topo;
      |             ^~~
bitaro.cpp:210:25: error: redefinition of 'std::vector<int> topo'
  210 | vector<int> adj[maxN+1],topo;
      |                         ^~~~
bitaro.cpp:11:25: note: 'std::vector<int> topo' previously declared here
   11 | vector<int> adj[maxN+1],topo;
      |                         ^~~~
bitaro.cpp:211:13: error: redefinition of 'std::vector<std::pair<int, int> > vec [100006]'
  211 | vector<pii> vec[maxN+1];
      |             ^~~
bitaro.cpp:12:13: note: 'std::vector<std::pair<int, int> > vec [100006]' previously declared here
   12 | vector<pii> vec[maxN+1];
      |             ^~~
bitaro.cpp:212:6: error: redefinition of 'bool vis [100006]'
  212 | bool vis[maxN+1];
      |      ^~~
bitaro.cpp:13:6: note: 'bool vis [100006]' previously declared here
   13 | bool vis[maxN+1];
      |      ^~~
bitaro.cpp:213:6: error: redefinition of 'void dfs(int)'
  213 | void dfs(int u)
      |      ^~~
bitaro.cpp:14:6: note: 'void dfs(int)' previously defined here
   14 | void dfs(int u)
      |      ^~~
bitaro.cpp:225:6: error: redefinition of 'void meg(int, int)'
  225 | void meg(int u,int v)
      |      ^~~
bitaro.cpp:26:6: note: 'void meg(int, int)' previously defined here
   26 | void meg(int u,int v)
      |      ^~~
bitaro.cpp: In function 'void meg(int, int)':
bitaro.cpp:237:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:237:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                            ~^~~~~~~~~~~~~~
bitaro.cpp:237:54: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  237 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                                             ~~~~~~~~~^~~~~~
bitaro.cpp:239:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:243:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:247:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |         if(i>=vec[u].size()||j>=vec[v].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp:247:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |         if(i>=vec[u].size()||j>=vec[v].size())
      |                              ~^~~~~~~~~~~~~~~
bitaro.cpp:265:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  265 |     while(i<vec[u].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:265:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  265 |     while(i<vec[u].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:267:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  267 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:271:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |         if(i>=vec[u].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp:278:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |     while(j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:278:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  278 |     while(j<vec[v].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:280:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  280 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:284:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  284 |         if(j>=vec[v].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp: At global scope:
bitaro.cpp:293:6: error: redefinition of 'void make()'
  293 | void make()
      |      ^~~~
bitaro.cpp:94:6: note: 'void make()' previously defined here
   94 | void make()
      |      ^~~~
bitaro.cpp:305:5: error: redefinition of 'int main()'
  305 | int main()
      |     ^~~~
bitaro.cpp:106:5: note: 'int main()' previously defined here
  106 | int main()
      |     ^~~~