제출 #424916

#제출 시각아이디문제언어결과실행 시간메모리
424916Mlxa슈퍼트리 잇기 (IOI20_supertrees)C++14
56 / 100
296 ms31912 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) x.begin(), x.end() #define mp make_pair #define mt make_tuple #define x first #define y second #include "supertrees.h" namespace my { const int N = 1010; int n, g[N][N], res[N][N]; void edge(int v, int u) { res[v][u] = true; res[u][v] = true; } vector<int> get_comp(int v, int msk) { static int lst[N], timer = 0; ++timer; lst[v] = timer; queue<int> q; vector<int> ret; q.push(v); while (q.size()) { v = q.front(); q.pop(); ret.push_back(v); for (int u = 0; u < n; ++u) { if (lst[u] == timer) { continue; } if ((msk >> g[v][u]) & 1) { lst[u] = timer; q.push(u); } } } return ret; } bool u1[N], u12[N]; } int construct(vector<vector<int>> _g) { using namespace my; n = (int)_g.size(); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { g[i][j] = _g[i][j]; if (g[i][j] == 3) { return 0; } } } for (int i = 0; i < n; ++i) { if (u12[i]) { continue; } vector<int> c12 = get_comp(i, (1 << 1) | (1 << 2)); // cout << "! " << c12.size() << endl; vector<int> cycle; for (int v : c12) { u12[v] = true; if (u1[v]) { continue; } vector<int> c1 = get_comp(v, 1 << 1); // cout << "? " << c1.size() << " " << c1[0] << endl; for (int u : c1) { for (int uu : c1) { if (g[u][uu] != 1) { return 0; } } u1[u] = true; } for (int u : c1) { for (int uu : c12) { if (u1[uu]) { continue; } if (g[u][uu] != 2) { return 0; } } } for (int idx = 0; idx + 1 < (int)c1.size(); ++idx) { edge(c1[idx], c1[idx + 1]); } cycle.push_back(c1.front()); } if (cycle.size() == 1) { continue; } for (int idx = 0; idx < (int)cycle.size(); ++idx) { edge(cycle[idx], cycle[(idx + 1) % cycle.size()]); } } vector<vector<int>> answer; for (int i = 0; i < n; ++i) { answer.push_back(vector<int>(res[i], res[i] + n)); } build(answer); return 1; } #ifdef LC #include "grader.cpp" #endif
#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...