제출 #300523

#제출 시각아이디문제언어결과실행 시간메모리
300523davitmarg슈퍼트리 잇기 (IOI20_supertrees)C++17
56 / 100
268 ms26264 KiB
/* DavitMarg In a honky-tonk, Down in Mexico */ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() #define fastIO ios::sync_with_stdio(false); cin.tie(0) using namespace std; const int N = 1005; #ifndef death #include "supertrees.h" #endif #ifdef death void build(vector<vector<int>> b) { for (int i = 0; i < b.size(); i++) { for (int j = 0; j < b.size(); j++) cout << b[i][j] << " "; cout << endl; } } #endif int parent[N]; void init(int n) { for (int i = 0; i < n; i++) parent[i] = i; } int par(int v) { if (v == parent[v]) return v; return parent[v] = par(parent[v]); } void dsu(int a, int b) { a = par(a); b = par(b); if (a == b) return; parent[b] = a; } int n,z; vector<vector<int>> ans,p; void add(int a, int b) { ans[a][b] = ans[b][a] = 1; } void solve(vector<int> v) { init(v.size()); for (int i = 0; i < v.size(); i++) for (int j = i + 1; j < v.size(); j++) if (p[v[i]][v[j]] == 1) dsu(i, j); /*for (int i = 0; i < v.size(); i++) for (int j = i + 1; j < v.size(); j++) if (p[v[i]][v[j]] == 2 && par(i) == par(j)) { z = 1; return; }*/ map<int, vector<int>> VS; vector<int> V; for (int i = 0; i < v.size(); i++) VS[v[par(i)]].PB(v[i]); for (auto it = VS.begin(); it != VS.end(); ++it) { for (int i = 0; i < it->second.size() - 1; i++) add(it->second[i], it->second[i + 1]); V.push_back(it->first); } if(V.size()>1) for (int i = 0; i < V.size(); i++) add(V[i], V[(i + 1) % V.size()]); } int construct(vector<vector<int>> P) { p = P; n = p.size(); ans.resize(n, vector<int>(n,0)); init(n); for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (p[i][j]) { dsu(i, j); if (p[i][j] == 3) return 0; } map<int, vector<int>> vs; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) if (p[i][j] == 0 && par(i) == par(j)) return 0; vs[par(i)].push_back(i); } for (auto it = vs.begin(); it != vs.end(); ++it) solve(it->second); if (z) return 0; build(ans); return 1; } #ifdef death int main() { fastIO; vector<vector<int>> P; int nn; cin >> nn; for (int i = 0; i < nn; i++) { P.push_back(vector<int>()); for (int j = 0; j < nn; j++) { int x; cin >> x; P[i].push_back(x); } } cout << construct(P) << endl; return 0; } #endif /* 4 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 */

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

supertrees.cpp: In function 'void solve(std::vector<int>)':
supertrees.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:87:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int j = i + 1; j < v.size(); j++)
      |                             ~~^~~~~~~~~~
supertrees.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int i = 0; i < it->second.size() - 1; i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int i = 0; i < V.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...