Submission #996401

#TimeUsernameProblemLanguageResultExecution timeMemory
996401phoenix슈퍼트리 잇기 (IOI20_supertrees)C++17
100 / 100
163 ms30216 KiB
#include<bits/stdc++.h> #include "supertrees.h" using namespace std; struct dsu { vector<int> p; vector<vector<int>> v; void init(int n) { p.resize(n); v.resize(n); for(int i = 0;i < n;i++) { p[ i ] = i; v[ i ].push_back({ i }); } } int find(int x) { return p[ x ] = (p[ x ] == x ? p[ x ] : find(p[ x ])); } void unite(int a, int b) { a = find(a); b = find(b); if(a == b) return; if(v[ a ].size() < v[ b ].size()) swap(a, b); for(int i = 0;i < v[ b ].size();i++) v[ a ].push_back(v[ b ][ i ]); p[ b ] = a; } }; const int N = 1000; vector<vector<int>> rs; vector<int> g[ N ]; int rt; bool visited[ N ]; int dfs(int s, int rt) { visited[ s ] = 1; for(int c : g[ s ]) { if(visited[ c ]) continue; rs[ s ][ c ] = 1; rs[ c ][ s ] = 1; return dfs(c, rt) + 1; } if(s != rt) { rs[ s ][ rt ] = 1; rs[ rt ][ s ] = 1; } return 1; } // void build(vector<vector<int>> p) { // for(auto c : p) { // for(int x : c) cout << x << ' '; // cout << '\n'; // } // } int construct(vector<vector<int>> p) { int n = p.size(); dsu ds; dsu ds0; ds.init(n); ds0.init(n); rs.resize(n, vector<int>(n)); vector<pair<int, int>> e[3]; for(int i = 0;i < n;i++) { for(int j = i + 1;j < n;j++) { if(p[ i ][ j ] == 3) return 0; if(p[ i ][ j ]) { ds0.unite(i, j); if(p[ i ][ j ] == 1) ds.unite(i, j); } e[p[ i ][ j ]].push_back({i, j}); } } for(pair<int, int> c : e[ 0 ]) if(ds0.find(c.first) == ds0.find(c.second)) return 0; for(pair<int, int> c : e[ 2 ]) if(ds.find(c.first) == ds.find(c.second)) return 0; else { g[ ds.find(c.first) ].push_back(ds.find(c.second)); g[ ds.find(c.second) ].push_back(ds.find(c.first)); } for(int i = 0;i < n;i++) { if(visited[ i ]) continue; if(dfs(i, i) == 2) return 0; } bool us[ n ] = {}; for(int i = 0;i < n;i++) { if(us[ i ]) continue; int x = ds.find(i); for(int to : ds.v[ x ]) { if(to == x) continue; us[ to ] = 1; rs[ x ][ to ] = 1; rs[ to ][ x ] = 1; } } build(rs); return 1; } // int main() { // int n; // cin >> n; // vector<vector<int>> p(n, vector<int>(n)); // for(int i = 0;i < n;i++) { // for(int j = 0;j < n;j++) { // cin >> p[i][j]; // } // } // cout << construct(p); // }

Compilation message (stderr)

supertrees.cpp: In member function 'void dsu::unite(int, int)':
supertrees.cpp:25:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i = 0;i < v[ b ].size();i++)
      |                       ~~^~~~~~~~~~~~~~~
#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...