Submission #1050143

#TimeUsernameProblemLanguageResultExecution timeMemory
1050143dozerConnecting Supertrees (IOI20_supertrees)C++14
100 / 100
165 ms22352 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define pb push_back #define pii pair<int, int> #define st first #define nd second #define sp " " #define endl "\n" #define LL node * 2 #define RR node * 2 + 1 #define ll long long #define N 200005 const int modulo = 1e9 + 7; const ll INF = 2e18 + 7; int construct(std::vector<std::vector<int>> p) { int n = p.size(); vector<vector<int>> adj(n, vector<int>(n, 0)); vector<int> done(n, 0), done2(n, 0), root(n, 0); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 3) return 0; for (int i = 0; i < n; i++) { if (done[i]) continue; done[i] = 1; root[i] = 1; for (int j = 0; j < n; j++){ if (j == i) continue; if (p[i][j] == 1){ if (done[j]) return 0; for (int k = 0; k < n; k++){ if (k == i || k == j) continue; if (p[i][k] != p[j][k]) return 0; } done[j] = 1; adj[i][j] = 1; adj[j][i] = 1; } } } for (int i = 0; i < n; i++){ if (root[i] == 0 || done2[i]) continue; vector<int> tmp; tmp.pb(i); done2[i] = 1; for (int j = 0; j < n; j++){ if (j == i || root[j] == 0 || p[i][j] != 2) continue; if (done2[j]) { return 0; } for (int k = 0; k < n; k++){ if (k == i || k == j) continue; if (root[k] == 1 && p[i][k] != p[j][k]) { return 0; } } tmp.pb(j); done2[j] = 1; } int m = tmp.size(); if (m == 1) continue; if (m == 2) return 0; for (int j = 0; j < m; j++){ int curr = tmp[j], nxt = tmp[(j + 1) % m]; adj[curr][nxt] = 1; adj[nxt][curr] = 1; } } build(adj); return 1; } /* static int n; static std::vector<std::vector<int>> p; static std::vector<std::vector<int>> b; static bool called = false; static void check(bool cond, std::string message) { if (!cond) { printf("%s\n", message.c_str()); fclose(stdout); exit(0); } } void build(std::vector<std::vector<int>> _b) { check(!called, "build is called more than once"); called = true; check((int)_b.size() == n, "Invalid number of rows in b"); for (int i = 0; i < n; i++) { check((int)_b[i].size() == n, "Invalid number of columns in b"); } b = _b; } int main() { fileio(); assert(scanf("%d", &n) == 1); p.resize(n); for (int i = 0; i < n; i++) { p[i].resize(n); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { assert(scanf("%d", &p[i][j]) == 1); } } fclose(stdin); int possible = construct(p); check(possible == 0 || possible == 1, "Invalid return value of construct"); if (possible == 1) { check(called, "construct returned 1 without calling build"); } else { check(!called, "construct called build but returned 0"); } printf("%d\n", possible); if (possible == 1) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j) { printf(" "); } printf("%d", b[i][j]); } printf("\n"); } } fclose(stdout); } */
#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...