Submission #1076816

#TimeUsernameProblemLanguageResultExecution timeMemory
1076816Hectorungo_18Connecting Supertrees (IOI20_supertrees)C++14
100 / 100
138 ms22100 KiB
#include "supertrees.h" #include <vector> #include<bits/stdc++.h> using namespace std; const int N = 1e3+7; int p[N]; int sz[N]; int pa(int u){ p[u]=(p[u] == u ? u : pa(p[u])); return p[u]; } bool sm(int u, int v){ return pa(u) == pa(v); } void un(int u, int v){ if(sm(u, v)) return; u = pa(u); v = pa(v); if(sz[v] > sz[u]) swap(u, v); sz[u]+=sz[v]; p[v]=u; } int construct(vector<vector<int>> v) { int n = v.size(); for(int i = 0; i <= n; i++){ p[i]=i; sz[i]=1; } for(int i = 0; i < n; i++){ bool ch = 0; if(pa(i)==i) ch = 1; for(int j = i+1; j < n; j++){ if(v[i][j] == 3) return 0; if(ch){ if(v[i][j] == 0) continue; if(pa(j) == j){ un(i, j); } else return 0; } else{ if(v[i][j] == 0){ if(pa(i) == pa(j)) return 0; } else if(pa(i) != pa(j)) return 0; } } } map<int, int> m; for(int i = 0; i < n; i++){ vector<int> a(4, 0); for(int j = 0; j < n; j++){ if(i == j) continue; a[v[i][j]]++; } if(a[1] > 0) m[i]=1; else if(a[2] > 0) m[i]=2; else if(a[3] > 0) m[i]=3; else m[i]=0; } vector<vector<int>> ans(n, vector<int> (n, 0)); vector<int> sp(n); for(int i = 0; i < n; i++){ sp[i]=pa(i); } for(int i = 0; i < n; i++){ p[i]=i; sz[i]=i; } for(int i = 0; i < n; i++){ if(sp[i] != i) continue; vector<int> w; for(int j = 0; j < n; j++){ if(sp[j] == i) w.push_back(j); } vector<int> dd; for(int j = 0; j < w.size(); j++){ int r = w[j]; for(int k = 0; k < n; k++){ if(k == r) continue; if(v[r][k] != 1) continue; if(pa(r) == pa(k)) continue; if(pa(r) == r){ un(r, k); } else{ if(pa(k) == k){ un(r, k); } else return 0; } } } for(int j = 0; j < w.size(); j++){ if(w[j] == pa(w[j])) dd.push_back(w[j]); } if(dd.size() == 2) return 0; for(int j = 1; j < dd.size(); j++){ ans[dd[j]][dd[j-1]] = 1; ans[dd[j-1]][dd[j]] = 1; } if(dd.size() > 2){ ans[dd[0]][dd.back()] = 1; ans[dd.back()][dd[0]] = 1; } vector<vector<int>> adj(n); for(int i = 0; i < w.size(); i++){ int r = w[i]; adj[pa(r)].push_back(r); } for(int i = 0; i < n; i++){ for(int j = 1; j < adj[i].size(); j++){ ans[adj[i][j]][adj[i][j-1]] = 1; ans[adj[i][j-1]][adj[i][j]] = 1; } } } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:89:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int j = 0; j < w.size(); j++){
      |                        ~~^~~~~~~~~~
supertrees.cpp:107:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int j = 0; j < w.size(); j++){
      |                        ~~^~~~~~~~~~
supertrees.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j = 1; j < dd.size(); j++){
      |                        ~~^~~~~~~~~~~
supertrees.cpp:120:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int i = 0; i < w.size(); i++){
      |                        ~~^~~~~~~~~~
supertrees.cpp:125:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             for(int j = 1; j < adj[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...