Submission #233736

#TimeUsernameProblemLanguageResultExecution timeMemory
233736MamedovKOVANICE (COI15_kovanice)C++14
0 / 100
99 ms16888 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define f first #define s second #define pb push_back using namespace std; const int up = 3e5 + 5; int n; int par[up], type[up], inDegree[up], root[up]; vector <pii> equals, lesses; vector <vector<int>> g; void extract(string &ACB, int &A, int &B, char &C) { A = B = 0; int i = 0; while(isdigit(ACB[i])) { A = 10 * A + ACB[i] - '0'; ++i; } C = ACB[i]; ++i; while(ACB[i] != '\0') { B = 10 * B + ACB[i] - '0'; ++i; } } int Find(int u) { return (par[u] < 0 ? u : par[u] = Find(par[u])); } void Union(int u, int v) { u = Find(u); v = Find(v); if(u != v) { if(par[u] > par[v]) { swap(u, v); } par[u] += par[v]; par[v] = u; } } void dfs(int node, int depth) { if(depth == n) { type[node] = n; } if(type[node]) return; type[node] = -1; for(int to : g[node]) { dfs(to, depth + 1); if(type[to]) { type[node] = type[to] - 1; } } } void solve() { ios_base::sync_with_stdio(false); int m, v, A, B; char C; string ACB; cin >> n >> m >> v; for(int i = 0; i < v; ++i) { cin >> ACB; extract(ACB, A, B, C); if(C == '=') { equals.pb({A, B}); }else { lesses.pb({A, B}); } } memset(par, -1, sizeof(par)); for(pii e : equals) { Union(e.f, e.s); } for(int i = 1; i <= m; ++i) { root[i] = Find(i); } g.resize(m + 1); for(pii l : lesses) { g[root[l.f]].pb(root[l.s]); ++inDegree[root[l.s]]; } return; for(int i = 1; i <= m; ++i) { if(i == root[i] && !inDegree[i]) dfs(i, 1); } for(int i = 1; i <= m; ++i) { if(type[root[i]] <= 0) { cout << '?' << '\n'; }else { cout << 'K' << type[root[i]] << '\n'; } } } int main() { solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...