Submission #731925

#TimeUsernameProblemLanguageResultExecution timeMemory
731925TheSahibConnecting Supertrees (IOI20_supertrees)C++17
0 / 100
1 ms308 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int MAX = 1005; int par[MAX]; int find_set(int v){ if(par[v] < 0) return v; return par[v] = find_set(par[v]); } bool unite(int u, int v){ u = find_set(u); v = find_set(v); if(u == v) return false; par[u] += par[v]; par[v] = u; return true; } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ans(n, vector<int>(n)); memset(par, -1, sizeof(par)); vector<bool> except(n, 0); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if(p[i][j] == 1){ except[i] = 1; ans[i][j] = 1; ans[j][i] = 1; } } } for (int i = 0; i < n; i++) { if(except[i]) continue; for (int j = 0; j < n; j++) { if(except[j]) continue; if(p[i][j] == 2){ unite(i, j); } } } vector<int> comps[MAX]; for (int i = 0; i < n; i++) { if(except[i]) continue; comps[find_set(i)].push_back(i); } for(auto& v:comps){ for (int i = 0; i < v.size(); i++) { if(i != 0){ ans[v[i]][v[i - 1]] = 1; } if(i != v.size() - 1){ ans[v[i]][v[i + 1]] = 1; } } if(v.size() > 1){ ans[v.front()][v.back()] = 1; ans[v.back()][v.front()] = 1; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(p[i][j] == 1 && unite(i, j)){ ans[i][j] = 1; ans[j][i] = 1; } } } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int i = 0; i < v.size(); i++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if(i != v.size() - 1){
      |                ~~^~~~~~~~~~~~~~~
#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...