Submission #1205737

#TimeUsernameProblemLanguageResultExecution timeMemory
120573712345678KOVANICE (COI15_kovanice)C++20
100 / 100
122 ms36920 KiB
#include <bits/stdc++.h> using namespace std; const int nx=3e5+5; int n, m, k, dsu[nx], degdn[nx], degup[nx], u, v, lvlup[nx], lvldn[nx], res[nx]; char opr; string s; vector<int> dn[nx], up[nx]; vector<pair<int, int>> edg; queue<int> q; int find(int x) { if (dsu[x]==x) return x; return dsu[x]=find(dsu[x]); } int tonum(string &x) { int res=0, sz=x.size(); for (int i=0; i<sz; i++) res*=10, res+=x[i]-'0'; return res; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m>>k; for (int i=1; i<=m; i++) dsu[i]=i; for (int i=0; i<k; i++) { cin>>s; int sz=s.size(); string a, b; opr=' '; for (int i=0; i<sz; i++) { if (s[i]=='<'||s[i]=='='||s[i]=='>') opr=s[i]; else { if (opr==' ') a.push_back(s[i]); else b.push_back(s[i]); } } u=tonum(a); v=tonum(b); if (opr=='=') dsu[find(u)]=find(v); else { if (opr=='<') edg.push_back({u, v}); else edg.push_back({v, u}); } } for (auto [u, v]:edg) up[find(u)].push_back(find(v)), degup[find(v)]++, dn[find(v)].push_back(find(u)), degdn[find(u)]++; for (int i=1; i<=m; i++) if (find(i)==i&&degup[i]==0) lvlup[i]=0, q.push(i); while (!q.empty()) { auto u=q.front(); q.pop(); for (auto v:up[u]) if (--degup[v]==0) lvlup[v]=max(lvlup[v], lvlup[u]+1), q.push(v); } for (int i=1; i<=m; i++) if (find(i)==i&&degdn[i]==0) lvldn[i]=0, q.push(i); while (!q.empty()) { auto u=q.front(); q.pop(); for (auto v:dn[u]) if (--degdn[v]==0) lvldn[v]=max(lvldn[v], lvldn[u]+1), q.push(v); } for (int i=1; i<=m; i++) if (find(i)==i&&lvlup[i]+lvldn[i]==n-1) res[i]=lvlup[i]+1; for (int i=1; i<=m; i++) { if (res[find(i)]) cout<<"K"<<res[find(i)]<<'\n'; else cout<<"?\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...