# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
846220 | 2023-09-07T12:35:16 Z | vjudge1 | KOVANICE (COI15_kovanice) | C++ | 2000 ms | 16452 KB |
#include <iostream> #include <vector> using namespace std; int n; int* valueofparent; int* parentindsu; bool* visited; vector<vector<int>> children; int getpindsu(int n){ if (parentindsu[n - 1] == n) return n; parentindsu[n - 1] = getpindsu(parentindsu[n - 1]); return parentindsu[n - 1]; } void dsumerge(int a, int b){ int pa = getpindsu(a); int pb = getpindsu(b); if (pa == pb) return; parentindsu[a - 1] = pb; parentindsu[pa - 1] = pb; } bool fill(int depth, int node){ if (depth == n){ valueofparent[node - 1] = n; return true; } if (visited[node - 1]){ if (valueofparent[node - 1] != -1) return true; } visited[node - 1] = true; bool isdetermined = false; for (int i = 0; i < children[node - 1].size(); i++){ if (fill(depth + 1, children[node - 1][i])) isdetermined = true; } if (isdetermined) valueofparent[node - 1] = depth; return isdetermined; } int main(){ int m, v, a, b; char c; string weigh; cin >> n >> m >> v; int equalcount = 0; int unequalcount = 0; int* equal1 = new int[v]; int* equal2 = new int[v]; int* less = new int[v]; int* more = new int[v]; for (int i = 0; i < v; i++){ cin >> a >> c >> b; if (c == '='){ equal1[equalcount] = a; equal2[equalcount] = b; equalcount++; } else { less[unequalcount] = a; more[unequalcount] = b; unequalcount++; } } parentindsu = new int[m]; for (int i = 0; i < m; i++) parentindsu[i] = i + 1; for (int i = 0; i < equalcount; i++){ dsumerge(equal1[i], equal2[i]); } bool *isattop = new bool[m]; for (int i = 1; i <= m; i++){ isattop[i - 1] = (getpindsu(i) == i); } children.resize(m); for (int i = 0; i < unequalcount; i++){ isattop[getpindsu(more[i]) - 1] = false; children[getpindsu(less[i]) - 1].push_back(getpindsu(more[i])); } valueofparent = new int[m]; visited = new bool[m]; for (int i = 0; i < m; i++){ valueofparent[i] = -1; visited[i] = false; } for (int i = 1; i <= m; i++){ if (isattop[i - 1]) fill(1, i); } for (int i = 1; i <= m; i++){ if (valueofparent[getpindsu(i) - 1] != -1){ cout << "K" << valueofparent[getpindsu(i) - 1] << endl; } else cout << "?\n"; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 348 KB | Output is correct |
2 | Correct | 2 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 195 ms | 9516 KB | Output is correct |
2 | Correct | 189 ms | 9628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2060 ms | 1624 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2037 ms | 16452 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |