Submission #392271

#TimeUsernameProblemLanguageResultExecution timeMemory
392271EnkognitConnecting Supertrees (IOI20_supertrees)C++14
0 / 100
1 ms460 KiB
#include <bits/stdc++.h> #include "supertrees.h" #define ll long long #define mp make_pair #define pb push_back #define all(x) x.begin(),x.end() #define pll pair<ll,ll> #define fi first #define se second #define pii pair<int,int> using namespace std; int d[1005][1005], T; vector<vector<int> > b; vector<int> c[2005], v[2005], e[2005]; bool tt[2005], tl[2005]; struct dsu { ll d[2005]; void make_sets(int h) { for (int i = 0; i < h; i++) d[i]=i; } ll find_set(int h) { if (h==d[h]) return h; else return d[h]=find_set(d[h]); } void unite_sets(int x,int y) { x=find_set(x); y=find_set(y); d[x]=y; } } g, gg; void dfs(int h) { tt[h]=1; d[T][h]++; for (int i = 0; i < c[h].size(); i++) if (!tt[c[h][i]]) { dfs(c[h][i]); } tt[h]=0; } bool check() { } int construct(vector<vector<int> > a) { ll n=a.size(); b.resize(n); for (int i = 0; i < n; i++) b[i].resize(n, 0); g.make_sets(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j]==1) g.unite_sets(i, j); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j]!=1 && g.find_set(i)==g.find_set(j)) { return 0; } vector<ll> z; for (int i = 0; i < n; i++) { if (g.find_set(i)==i) { z.pb(i); } v[g.find_set(i)].pb(i); } for (int i = 0; i < z.size(); i++) { for (int u = 0; u < v[z[i]].size()-1; u++) { b[v[z[i]][u+1]][v[z[i]][u]]=1; b[v[z[i]][u]][v[z[i]][u+1]]=1; c[v[z[i]][u+1]].pb(v[z[i]][u]); c[v[z[i]][u]].pb(v[z[i]][u+1]); } } gg.make_sets(n); for (int i = 0; i < z.size(); i++) for (int j = 0; j < z.size(); j++) { ll p=-1; for (int u = 0; u < v[z[i]].size(); u++) for (int q = 0; q < v[z[j]].size(); q++) if (p==-1) p=a[v[z[i]][u]][v[z[j]][q]]; else if (p!=a[v[z[i]][u]][v[z[j]][q]]) return 0; if (p==2) gg.unite_sets(z[i], z[j]); } for (int i = 0; i < z.size(); i++) for (int j = 0; j < z.size(); j++) { ll p=-1; for (int u = 0; u < v[z[i]].size(); u++) for (int q = 0; q < v[z[j]].size(); q++) if (p==-1) p=a[v[z[i]][u]][v[z[j]][q]]; else if (p!=a[v[z[i]][u]][v[z[j]][q]]) return 0; if (p==0 && gg.find_set(z[i])==gg.find_set(z[j])) return 0; } for (int i = 0; i < z.size(); i++) e[gg.find_set(z[i])].pb(z[i]); for (int i = 0; i < z.size(); i++) if (gg.find_set(z[i])==z[i]) { for (int j = 0; j < e[z[i]].size(); j++) { ll u=(j+1)%((int)e[z[i]].size()); b[e[z[i]][j]][e[z[i]][u]]=1; b[e[z[i]][u]][e[z[i]][j]]=1; c[e[z[i]][j]].pb(e[z[i]][u]); c[e[z[i]][u]].pb(e[z[i]][j]); } } build(b); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:45:23: 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 < c[h].size(); i++)
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp: In function 'bool check()':
supertrees.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
   56 | }
      | ^
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int u = 0; u < v[z[i]].size()-1; u++)
      |                         ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int j = 0; j < z.size(); j++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for (int u = 0; u < v[z[i]].size(); u++)
      |                         ~~^~~~~~~~~~~~~~~~
supertrees.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int q = 0; q < v[z[j]].size(); q++)
      |                             ~~^~~~~~~~~~~~~~~~
supertrees.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for (int j = 0; j < z.size(); j++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (int u = 0; u < v[z[i]].size(); u++)
      |                         ~~^~~~~~~~~~~~~~~~
supertrees.cpp:116:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for (int q = 0; q < v[z[j]].size(); q++)
      |                             ~~^~~~~~~~~~~~~~~~
supertrees.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |             for (int j = 0; j < e[z[i]].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...