제출 #301475

#제출 시각아이디문제언어결과실행 시간메모리
30147512tqian슈퍼트리 잇기 (IOI20_supertrees)C++14
96 / 100
263 ms22264 KiB
#ifdef LOCAL #else #include "supertrees.h" #endif #include<bits/stdc++.h> using namespace std; typedef long long ll; #ifdef LOCAL #define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__); #else #define dbg(...) 17; #endif template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; } template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr> ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; } template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; } template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); } #ifdef LOCAL bool build(vector<vector<int>> p) { return true; } #else #endif int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> res(n, vector<int>(n, 0)); vector<bool> vis(n); auto ae = [&](int u, int v) { res[u][v] = 1; res[v][u] = 1; }; auto make_cycle = [&](vector<int>& v) { for (int i = 0; i < v.size(); i++) { ae(v[i], v[(i + 1) % v.size()]); } }; auto make_triple = [&](vector<int>& v) { make_cycle(v); ae(v[0], v[1]); }; auto make_chain = [&](vector<int>& v) { for (int i = 0; i < v.size() - 1; i++) { ae(v[i], v[i + 1]); } }; for (int i = 0; i < n; i++) { if (vis[i]) continue; vector<int> comp; function<void(int)> dfs_comp = [&](int src) { vis[src] = true; comp.push_back(src); for (int nxt = 0; nxt < n; nxt++) { if (p[src][nxt] == 0 || vis[nxt]) continue; dfs_comp(nxt); } }; dfs_comp(i); int sz = comp.size(); vector<int> overall(4); vector<int> one; vector<int> other; for (int x: comp) { vector<int> cnt(4); for (int y: comp) { if (x == y) continue; cnt[p[x][y]]++; overall[p[x][y]]++; } if (cnt[0]) { return 0; } if (cnt[1] == 0) { other.push_back(x); } else { one.push_back(x); } } if (overall[0] || overall[2] && overall[3]) { return 0; } if (overall[2] == 0 && overall[3] == 0) { vector<int> big; for (int x: one) big.push_back(x); for (int x: other) big.push_back(x); make_chain(big); continue; } vector<vector<int>> chains; for (int x: one) { bool done = false; for(auto& y: chains) { bool ok = false; for (int z: y) { if (p[x][z] != 1) { ok = true; break; } } if (ok == false) { y.push_back(x); done = true; break; } } if (done == false) { chains.push_back(vector<int>(0)); chains.back().push_back(x); } } for (auto& c: chains) { for (int x: c) { for (int y: c) { if (p[x][y] != 1) { return 0; } } } } for (int j = 0; j < chains.size(); j++) { for (int k = j + 1; k < chains.size(); k++) { for (int x: chains[j]) { for (int y: chains[k]) { if (p[x][y] == 1) { return 0; } } } } } int cycle = chains.size() + other.size(); if (overall[2]) { if (cycle < 3) { return 0; } for (auto x: chains) { other.push_back(x[0]); make_chain(x); } make_cycle(other); } else if (overall[3]) { if (cycle < 4) { return 0; } for (auto x: chains) { other.push_back(x[0]); make_chain(other); } make_triple(other); } else { vector<int> big; for (int x: one) big.push_back(x); for (int x: other) big.push_back(x); make_chain(big); } } build(res); return 1; } #ifdef LOCAL int main() { freopen("file.in", "r", stdin); int n; cin >> n; vector<vector<int>> p(n, vector<int>(n, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> p[i][j]; } } cout << construct(p) << '\n'; return 0; } #else #endif

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

supertrees.cpp: In lambda function:
supertrees.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
supertrees.cpp: In lambda function:
supertrees.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < v.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:80:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   80 |         if (overall[0] || overall[2] && overall[3]) {
supertrees.cpp:121:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for (int j = 0; j < chains.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
supertrees.cpp:122:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for (int k = j + 1; k < chains.size(); k++) {
      |                                 ~~^~~~~~~~~~~~~~~
supertrees.cpp:60:13: warning: unused variable 'sz' [-Wunused-variable]
   60 |         int sz = comp.size();
      |             ^~
#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...