제출 #837196

#제출 시각아이디문제언어결과실행 시간메모리
837196QwertyPi열쇠 (IOI21_keys)C++17
0 / 100
20 ms42584 KiB
#include <bits/stdc++.h> using namespace std; const int N_MAX = 3e5 + 11; struct edge{ int to, c; bool operator< (const edge& o) const { return c < o.c || (c == o.c && to < o.to); } }; set<int> _vertexes[N_MAX]; set<int> _keys[N_MAX]; set<edge> _edges[N_MAX]; struct node{ set<int>* vertexes; set<int>* keys; set<edge>* edges; int find_next(); void clear(); } nodes[N_MAX]; int prv[N_MAX], _size[N_MAX]; bool vis[N_MAX], done[N_MAX]; void fill_none(int v){ int x = v; while(!done[x]){ done[x] = true; _size[x] = 1 << 30; x = prv[v]; } } int back_number = -1; void node::clear(){ vertexes->clear(); keys->clear(); edges->clear(); } int node::find_next(){ for(auto [u, c] : *edges){ if(keys->count(c) && !vertexes->count(u)){ edges->erase({u, c}); return u; } } return -1; } void merge(int u, int v){ for(auto x : *nodes[v].vertexes){ nodes[u].vertexes->insert(x); } for(auto x : *nodes[v].keys){ nodes[u].keys->insert(x); } for(auto e : *nodes[v].edges){ nodes[u].edges->insert(e); } } void dfs(int v, int pa = -1){ vis[v] = true; while(true){ int u = nodes[v].find_next(); if(u == -1) break; if(done[u]) { fill_none(v); } else if(vis[u]) { back_number = u; merge(prv[v], v); return; } else { prv[u] = v; dfs(u, v); if(back_number != -1){ if(v == back_number){ back_number = -1; }else{ merge(prv[v], v); return; } } } } for(auto u : *nodes[v].vertexes){ if(!done[u]) { done[u] = true; _size[u] = nodes[v].vertexes->size(); } } fill_none(prv[v]); } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { int n = r.size(), m = u.size(); vector<int> ans(n); for(int i = 0; i < n; i++){ nodes[i].vertexes = &_vertexes[i]; nodes[i].keys = &_keys[i]; nodes[i].edges = &_edges[i]; } for(int i = 0; i < n; i++) nodes[i].vertexes->insert(i); for(int i = 0; i < n; i++) nodes[i].keys->insert(r[i]); for(int i = 0; i < m; i++) { nodes[u[i]].edges->insert({v[i], c[i]}); nodes[v[i]].edges->insert({u[i], c[i]}); } for(int i = 0; i < n; i++){ if(!vis[i]){ dfs(i); } } int min_size = *min_element(_size, _size + n); for(int i = 0; i < n; i++){ ans[i] = _size[i] == min_size; } 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...