Submission #233744

#TimeUsernameProblemLanguageResultExecution timeMemory
233744MamedovKOVANICE (COI15_kovanice)C++14
100 / 100
218 ms29552 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], dis[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 dfs1(int node) { if(dis[node]) return; dis[node] = 1; for(int to : g[node]) { dfs1(to); dis[node] = max(dis[node], dis[to] + 1); } } void dfs2(int node) { if(type[node]) return; type[node] = dis[node]; for(int to : g[node]) { if(dis[to] == dis[node] - 1) { dfs2(to); } } } 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.s]].pb(root[l.f]); ++inDegree[root[l.f]]; } for(int i = 1; i <= m; ++i) { if(i == root[i] && !inDegree[i]) dfs1(i); } for(int i = 1; i <= m; ++i) { if(dis[i] == n) dfs2(i); } for(int i = 1; i <= m; ++i) { if(!type[root[i]]) { 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...