Submission #671690

#TimeUsernameProblemLanguageResultExecution timeMemory
671690flappybirdKeys (IOI21_keys)C++17
0 / 100
3112 ms2097152 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") using namespace std; typedef pair<int, int> pii; #define MAX 301010 int N, M; int cycle_chk[MAX]; int find_cycle(int v) { if (cycle_chk[v] == v) return v; else return cycle_chk[v] = find_cycle(cycle_chk[v]); } void merge_cycle(int u, int v) { u = find_cycle(u); v = find_cycle(v); cycle_chk[u] = v; } int p[MAX]; int num[MAX]; set<int> keys[MAX]; queue<int> adj[MAX]; map<int, vector<int>> mp[MAX]; int nxt[MAX]; vector<int> subv[MAX]; #define exists(st, v) (st.find(v) != st.end()) int find(int v) { if (p[v] == v) return v; return p[v] = find(p[v]); } queue<pii> lst; int mn; vector<int> mlist; void merge(int u, int v) { u = find(u); v = find(v); if (u == v) return; if (keys[u].size() > keys[v].size()) swap(u, v); p[u] = v; if (subv[u].size() > subv[v].size()) swap(subv[u], subv[v]); for (auto x : subv[u]) subv[v].push_back(x); num[v] += num[u]; for (auto x : keys[u]) { keys[v].insert(x); if (exists(mp[v], x)) { for (auto nxt : mp[v][x]) adj[v].push(find(nxt)); mp[v].erase(x); } } for (auto& [x, vec] : mp[u]) { if (exists(keys[v], x)) for (auto nxt : vec) adj[v].push(find(nxt)); else for (auto nxt : vec) mp[v][x].push_back(find(nxt)); } while (adj[u].size()) adj[v].push(adj[u].front()), adj[u].pop(); while (adj[v].size()) { int t = adj[v].front(); if (find(t) != find(v)) { nxt[v] = t; if (find_cycle(t) == find_cycle(v)) { int loc = t; int pv = t; while (find(loc) != find(v)) { loc = nxt[loc]; loc = find(loc); lst.emplace(loc, pv); pv = loc; } } else merge_cycle(t, v); break; } else adj[v].pop(); } if (adj[v].empty()) { if (mn > num[v]) { mlist = subv[v]; mn = num[v]; } else if (mn == num[v]) mlist.insert(mlist.end(), subv[v].begin(), subv[v].end()); } } vector<int> radj[MAX]; std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) { N = R.size(); M = U.size(); int i; for (i = 0; i < N; i++) p[i] = i, num[i] = 1, cycle_chk[i] = i, keys[i].emplace(R[i]), subv[i].push_back(i); mn = N; for (i = 0; i < M; i++) radj[U[i]].push_back(i), radj[V[i]].push_back(i); auto to = [&](int v, int e) { return U[e] + V[e] - v; }; for (i = 0; i < N; i++) { for (auto e : radj[i]) { if (C[e] == R[i]) adj[i].emplace(to(i, e)); else mp[i][C[e]].push_back(to(i, e)); } } for (i = 0; i < N; i++) { nxt[i] = -1; if (adj[i].size()) nxt[i] = adj[i].front(); } for (i = 0; i < N; i++) { if (~nxt[i]) { int t = nxt[i]; if (find_cycle(t) == find_cycle(i)) { int loc = t; int pv = t; while (find(loc) != find(i)) { loc = nxt[loc]; loc = find(loc); lst.emplace(loc, pv); pv = loc; } } else merge_cycle(i, t); } else { mn = 1; mlist.push_back(i); } } while (lst.size()) { int u, v; tie(u, v) = lst.front(); lst.pop(); merge(u, v); } vector<int> ansv(N); for (auto p : mlist) ansv[p] = 1; return ansv; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...