제출 #979406

#제출 시각아이디문제언어결과실행 시간메모리
979406alontanay열쇠 (IOI21_keys)C++17
20 / 100
505 ms287820 KiB
#include "keys.h" #include <bits/stdc++.h> #define f first #define s second #define NEW_STATE 0 #define ACTIVE_STATE 1 #define OLD_STATE 2 #define NO_POS -1 using namespace std; using pi = pair<int,int>; const int MAX_N = 3e5+5; namespace dsu { int sz[MAX_N], root[MAX_N], L[MAX_N]; int PTR_pos[MAX_N]; stack<int> pos[MAX_N]; int PTR_ord_future[MAX_N]; set<pi,greater<pi>> ord_future[MAX_N]; void init(int n) { for(int i = 0; i < n; i ++) { sz[i] = 1; root[i] = i; PTR_pos[i] = i; PTR_ord_future[i] = i; } } int get_root(int node) { if(root[node] == node) {return node;} return root[node] = get_root(root[node]); } void add_pos(int node, int ne) { pos[PTR_pos[get_root(node)]].push(ne); } int poll_pos(int node) { int ptr = PTR_pos[get_root(node)]; if(pos[ptr].empty()) { return NO_POS; } int top = pos[ptr].top(); pos[ptr].pop(); return top; } bool are_joined(int a, int b) { return get_root(a) == get_root(b); } int merge(int a, int b) { a = get_root(a); b = get_root(b); if(a == b) { return a; } if(sz[a] < sz[b]) { swap(a,b); } L[a] = min(L[a],L[b]); root[b] = a; { int big_ptr = PTR_pos[a]; int small_ptr = PTR_pos[b]; if(pos[big_ptr].size() < pos[small_ptr].size()) { swap(big_ptr,small_ptr); } PTR_pos[a] = big_ptr; stack<int> &big_pos = pos[big_ptr]; stack<int> &small_pos = pos[small_ptr]; while(!small_pos.empty()) { big_pos.push(small_pos.top()); small_pos.pop(); } } { int big_ptr = PTR_ord_future[a]; int small_ptr = PTR_ord_future[b]; if(ord_future[big_ptr].size() < ord_future[small_ptr].size()) { swap(big_ptr,small_ptr); } PTR_ord_future[a] = big_ptr; set<pi,greater<pi>> &big_ord_future = ord_future[big_ptr]; set<pi,greater<pi>> &small_ord_future = ord_future[small_ptr]; big_ord_future.insert(small_ord_future.begin(),small_ord_future.end()); small_ord_future.clear(); while(!big_ord_future.empty() && big_ord_future.begin()->f >= L[a]) { pos[big_ptr].push(big_ord_future.begin()->s); big_ord_future.erase(big_ord_future.begin()); } } return a; } } vector<pi> nei[MAX_N]; vector<pi> need_key[MAX_N]; int state[MAX_N]; std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { int n = r.size(), m = u.size(); dsu::init(n); for(int i = 0;i < m; i ++) { int a = u[i], b = v[i], t = c[i]; nei[a].push_back({b,t}); nei[b].push_back({a,t}); } vector<int> last_occ(n); int cidx = 0; vector<int> res; int opt_score = n; for(int i = 0; i < n; i ++) { if(state[i] != NEW_STATE) { continue; } stack<int> UPD_need_key; stack<int> reached_nodes; bool reached_old = false; int node = i; stack<int> comp_stack; while(true) { cidx++; reached_nodes.push(node); int key = r[node]; dsu::L[node] = cidx; comp_stack.push(node); last_occ[key] = cidx; state[node] = ACTIVE_STATE; for(auto &[ne, req] : nei[node]) { UPD_need_key.push(req); need_key[req].push_back({node,ne}); dsu::ord_future[node].insert({last_occ[req],ne}); } for(pi edge : need_key[key]) { dsu::add_pos(edge.f,edge.s); } need_key[key].clear(); int next_node; bool converged = false; while(true) { next_node = dsu::poll_pos(node); if(next_node == NO_POS) { converged = true; break; } if(state[next_node] == OLD_STATE) { reached_old = true; break; } if(state[next_node] == NEW_STATE) { break; } while(comp_stack.size() >= 2 && !dsu::are_joined(node,next_node)) { int top = comp_stack.top(); comp_stack.pop(); int bef = comp_stack.top(); comp_stack.pop(); int new_root = dsu::merge(top,bef); comp_stack.push(new_root); } } if(reached_old || converged) { break; } node = next_node; } vector<int> base_comp; base_comp.reserve(reached_nodes.size()); while(!reached_nodes.empty()) { int top = reached_nodes.top(); if(!reached_old && dsu::are_joined(node, top)) { base_comp.push_back(top); } reached_nodes.pop(); state[top] = OLD_STATE; } if(!reached_old) { int score = base_comp.size(); if(score < opt_score) { opt_score = score; res.clear(); } if(score == opt_score) { res.insert(res.begin(),base_comp.begin(),base_comp.end()); } } while(!UPD_need_key.empty()) { int key = UPD_need_key.top(); UPD_need_key.pop(); need_key[key].clear(); } } vector<int> ans(n); for(int r : res) { ans[r] = 1; } return ans; }
#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...