Submission #1315729

#TimeUsernameProblemLanguageResultExecution timeMemory
1315729rahidilbayramliConnecting Supertrees (IOI20_supertrees)C++20
11 / 100
93 ms22016 KiB
#include<bits/stdc++.h> #include "supertrees.h" #define ll long long #define ld long double #define vl vector<ll> #define vi vector<int> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define sz(v) (int)(v.size()) #define f first #define s second #define pii pair<int, int> #define pll pair<ll, ll> using namespace std; const int sz = 1e3+5; int usize[sz], par[sz]; void makeset(int v) { par[v] = v; usize[v] = 1; } int findpar(int v) { if(par[v] == v) return v; return par[v] = findpar(par[v]); } void unionsets(int a, int b) { a = findpar(a); b = findpar(b); if(a != b) { if(usize[a] > usize[b]) swap(a, b); par[b] = a; usize[a] += usize[b]; } } int construct(vector<vector<int>>p) { int n = sz(p); int cnt = 0, cnt2 = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cnt += p[i][j]; cnt2 += (p[i][j] <= 1); } } if(cnt == n * n) { vector<vector<int>>answer; for(int i = 0; i < n; i++) { vector<int>row; for(int j = 0; j < n; j++) { if(j == i + 1 || j == i - 1) row.pb(1); else row.pb(0); } answer.pb(row); } build(answer); return 1; } if(cnt2 == n * n) { for(int i = 0; i < n; i++) makeset(i); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(i == j) continue; int u = i, v = j; u = findpar(u); v = findpar(v); if(u == v && p[i][j] == 0) { return 0; } if(p[i][j] == 1) unionsets(i, j); } } vl v[n]; int grid[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) grid[i][j] = 0; } for(int i = 0; i < n; i++) { int u = i; u = findpar(u); grid[u][i] = 1; grid[i][u] = 1; } vector<vector<int>>answer; for(int i = 0; i < n; i++) { vector<int>row; for(int j = 0; j < n; j++) row.pb(grid[i][j]); answer.pb(row); } build(answer); return 1; } }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:117:1: warning: control reaches end of non-void function [-Wreturn-type]
  117 | }
      | ^
#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...