제출 #683763

#제출 시각아이디문제언어결과실행 시간메모리
683763sharaelong슈퍼트리 잇기 (IOI20_supertrees)C++17
56 / 100
215 ms24180 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; struct DisjointSet { int n; vector<int> parent, rank; DisjointSet(int _n) : n(_n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); rank.resize(n, 0); } int find(int u) { return parent[u] = (u == parent[u] ? u : find(parent[u])); } void merge(int u, int v) { u = find(u); v = find(v); if (u == v) return; if (rank[u] > rank[v]) swap(u, v); parent[u] = v; if (rank[u] == rank[v]) ++rank[v]; } }; int construct(vector<vector<int>> p) { int n = p.size(); for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) { if (p[i][j] == 3) { return 0; } } } DisjointSet dsu(n); DisjointSet dsu2(n); for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) { if (p[i][j] >= 1) { dsu.merge(i, j); } if (p[i][j] == 1) { dsu2.merge(i, j); } } } for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) { if (i != j) { if (dsu.find(i) == dsu.find(j) && p[i][j] == 0) return 0; if (dsu2.find(i) == dsu2.find(j) && p[i][j] == 2) return 0; if (dsu.find(i) == dsu.find(j) && dsu2.find(i) != dsu2.find(j) && p[i][j] != 2) return 0; } } } vector<vector<int>> ans(n, vector<int>(n, 0)); vector<vector<int>> trees(n); for (int i=0; i<n; ++i) trees[dsu2.find(i)].push_back(i); for (int i=0; i<n; ++i) { // for (int x: trees[i]) cout << x << ' '; // cout << endl; for (int j=0; j+1<trees[i].size(); ++j) { int x = trees[i][j]; int y = trees[i][j+1]; ans[x][y] = ans[y][x] = 1; } } vector<vector<int>> comps(n); for (int i=0; i<n; ++i) { if (!trees[i].empty()) { comps[dsu.find(trees[i][0])].push_back(trees[i][0]); } } for (int i=0; i<n; ++i) { // for (int x: comps[i]) cout << x << ' '; // cout << endl; for (int j=0; j+1<comps[i].size(); ++j) { int x = comps[i][j]; int y = comps[i][j+1]; ans[x][y] = ans[y][x] = 1; } if (comps[i].size() >= 2) ans[comps[i][0]][comps[i].back()] = ans[comps[i].back()][comps[i][0]] = 1; } build(ans); return 1; }

컴파일 시 표준 에러 (stderr) 메시지

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