제출 #989111

#제출 시각아이디문제언어결과실행 시간메모리
989111LOLOLOKOVANICE (COI15_kovanice)C++17
100 / 100
97 ms28100 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 3e5 + 10; struct DSU{ vector <int> p, sz; void ass(int n) { p.assign(n + 1, 0); sz.assign(n + 1, 1); } int get(int a) { return p[a] ? get(p[a]) : a; } void unite(int a, int b) { a = get(a), b = get(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); sz[a] += sz[b]; p[b] = a; } } D; vector <pair <int, int>> save; vector <int> ed[N]; void dfs(int u, vector <int> &f) { if (f[u] != -1) return; f[u] = 1; for (auto x : ed[u]) { if (f[x] == -1) dfs(x, f); f[u] = max(f[u], f[x] + 1); } } int m; vector <int> process(vector <pair <int, int>>& save) { for (int i = 1; i <= m; i++) ed[i].clear(); vector <int> f(m + 1, -1); for (auto x : save) { ed[D.get(x.f)].pb(D.get(x.s)); } for (int i = 1; i <= m; i++) { int t = D.get(i); if (f[t] == -1) dfs(t, f); } return f; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, v; cin >> n >> m >> v; D.ass(m + 1); for (int i = 0; i < v; i++) { int a, c; char b; cin >> a >> b >> c; if (b == '=') { D.unite(a, c); continue; } if (b == '>') swap(a, c); save.pb({a, c}); } vector <int> f1 = process(save); for (auto &x : save) swap(x.s, x.f); vector <int> f2 = process(save); for (int i = 1; i <= m; i++) { int t = D.get(i); if (f1[t] + f2[t] == n + 1) { cout << "K" << f2[t] << '\n'; } else { cout << "?\n"; } } return 0; } /* 5 4 3 1 4 2 1 2 3 2 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...