제출 #1183646

#제출 시각아이디문제언어결과실행 시간메모리
1183646harvsftw낙하산 고리들 (IOI12_rings)C++20
52 / 100
1592 ms320756 KiB
#include <bits/stdc++.h> using namespace std; #define F(i, n) for (int i = 0; i < (n); i++) #define F_reverse(i, n) for (int i = (n - 1); i >= 0; i--) #define N 1000000 /* ideas deleting a node should result in graph where max degree is 2, and no cycles so if there are nodes with degree >= 3, the node needs to be connected to all other instances only 1 component can have degree 3/4 case max node with upto degree >= 4: only one with deg >= 4 can occur (otherwise no critical), and it is the only one that can be critical it can be connected to O(n) nodes with degree 3 case node with upto degree == 3: at most 4 3degs can occur (otherwise no critical), (3deg connected to 3 3degs) only possible crits are them and nodes connected to them (around 16 max?) based from hints 1. state machine that based on max deg node from 2 -> 3 -> 4+ 1. if there are <= 4 3degs, naively create multiple graphs without a specific node, and ensure they have no cycle 2. the 5th 3deg and above: skip creating sans that node-graphs their neighbors 3. the moment the 1st 4deg is created: replace graphs with sans that node graph case node with upto degree == 2 only: ensure upto one cycle only impl: everthing in the connected component is crit can store count of connected components with cycles */ struct dsu_clean { int p[N]; // parent node int sz[N]; // size of component void init(int n) { F(i, n) { p[i] = i; sz[i] = 1; } } int find(int x) { if (p[x] == x) { return x; } int ret = find(p[x]); p[x] = ret; return ret; } bool united(int a, int b) { int x = find(a); int y = find(b); return x == y; } void unite(int a, int b) { int x = find(a); int y = find(b); if (x != y) { if (sz[x] < sz[y]) { swap(x, y); } p[y] = x; sz[x] += sz[y]; } } }; int n; vector<pair<int, int>> link_list; // not to be confused with a linked list //struct graph_sans_specific_node; struct graph_sans_specific_node { dsu_clean dsu; bool has_cycle_flag = false; int excl_node; graph_sans_specific_node(int excl_node) { dsu.init(n); this->excl_node = excl_node; for(auto [u, v] : link_list) { process_input(u, v); } }; void process_input(int u, int v) { //cout << excl_node << " recv " << u << " " << v << endl; if(u != excl_node && v != excl_node) { if(dsu.united(u, v)) { ////cout << "has cycle" << endl; this->has_cycle_flag = true; } else { dsu.unite(u, v); } } } }; unordered_map<int, graph_sans_specific_node> graphs_without_specific_nodes; struct dsu_main { int p[N]; // parent node int sz[N]; // size of component // stats int components_with_3deg = 0, components_with_4plusdeg = 0, components_with_cycles = 0; int component_with_cycle; // misc params int num_4plus_deg[N]; int v_4plus_deg[N]; // assumes one only bool has_cycle[N]; // limit to 4 vector<unordered_set<int>> v_3_deg; void init(int n) { F(i, n) { p[i] = i; sz[i] = 1; } v_3_deg.resize(n); } int find(int x) { if (p[x] == x) { return x; } int ret = find(p[x]); p[x] = ret; return ret; } void unite(int a, int b) { int x = find(a); int y = find(b); if (x != y) { if (sz[x] < sz[y]) { swap(x, y); } components_with_4plusdeg -= num_4plus_deg[x] > 0; components_with_4plusdeg -= num_4plus_deg[y] > 0; components_with_3deg -= v_3_deg[x].size() > 0; components_with_3deg -= v_3_deg[y].size() > 0; components_with_cycles -= has_cycle[x]; components_with_cycles -= has_cycle[y]; p[y] = x; sz[x] += sz[y]; num_4plus_deg[x] += num_4plus_deg[y]; if (num_4plus_deg[x] == 0 && num_4plus_deg[y] > 0) { // move to x v_4plus_deg[x] = v_4plus_deg[y]; } if(num_4plus_deg[x] > 0) { components_with_4plusdeg++; } for (int v : v_3_deg[y]) { if (v_3_deg[x].size() == 4) { break; } v_3_deg[x].insert(v); } if(v_3_deg[x].size() > 0) { components_with_3deg++; } has_cycle[x] |= has_cycle[y]; if(has_cycle[x]) { components_with_cycles++; component_with_cycle = x; } } } } dsu; struct vertex_info { bool in_cyle; vector<int> edge_list; unordered_set<int> _3deg_neighbors; size_t count_3deg_neighbors() { return _3deg_neighbors.size(); } bool is_3deg() { return edge_list.size() == 3; } }; vector<vertex_info> info(N); unordered_set<int> get_3deg_and_neighbors(int u) { unordered_set<int> nodes, vis; int p = dsu.find(u); for (auto v : dsu.v_3_deg[p]) { //cout << v << " has 3 edges" << endl; for (auto u : info[v].edge_list) { // if(vis.contains(u)) { // continue; // } // vis.insert(u); nodes.insert(u); } nodes.insert(v); } return nodes; } void Init(int N_) { dsu.init(N_); n = N_; } size_t _3deg_node_cnt = 0, _4plusdeg_node_cnt = 0; int dbg; void Link(int A, int B) { link_list.emplace_back(A, B); for(auto& [_, g] : graphs_without_specific_nodes) { // note & is needed g.process_input(A, B); } int u = dsu.find(A), v = dsu.find(B); if(u == v && !dsu.has_cycle[u]) { // cycle detected dsu.has_cycle[u] = true; dsu.components_with_cycles++; dsu.component_with_cycle = u; } // //cout << A << ' ' << B << endl; info[A].edge_list.push_back(B); info[B].edge_list.push_back(A); auto handle_changes = [&](int u, int dsu_rep) { int deg = info[u].edge_list.size(); if (deg == 3) { for (int v : info[u].edge_list) { info[v]._3deg_neighbors.insert(u); } if(dsu.v_3_deg[dsu_rep].size() == 0) { dsu.components_with_3deg++; } if(dsu.v_3_deg[dsu_rep].size() < 4) { // anti-TLE dsu.v_3_deg[dsu_rep].insert(u); } _3deg_node_cnt++; if(_4plusdeg_node_cnt == 0 && _3deg_node_cnt <= 4) { auto community = get_3deg_and_neighbors(u); for(int v : community) { if(graphs_without_specific_nodes.find(v) == graphs_without_specific_nodes.end()) { graphs_without_specific_nodes.emplace(v, graph_sans_specific_node(v)); } } } } else if (deg == 4) { for (int v : info[u].edge_list) { info[v]._3deg_neighbors.erase(u); } dsu.v_3_deg[dsu_rep].erase(u); if(dsu.num_4plus_deg[dsu_rep]++ == 0) dsu.components_with_4plusdeg++; dsu.v_4plus_deg[dsu_rep] = u; _3deg_node_cnt--; _4plusdeg_node_cnt++; if(_4plusdeg_node_cnt == 1) { graphs_without_specific_nodes.clear(); graphs_without_specific_nodes.emplace(u, graph_sans_specific_node(u)); } } }; if(_3deg_node_cnt <= 4 && _4plusdeg_node_cnt <= 1) { // this operation is very expensive if(3 <= info[A].edge_list.size() && info[A].edge_list.size() <= 4) handle_changes(A, u); if(3 <= info[B].edge_list.size() && info[B].edge_list.size() <= 4) handle_changes(B, v); } dsu.unite(A, B); //cout << ++dbg << endl; // //cout << "components with 3deg: " << components_with_3deg.size() << endl; // //cout << "components with 4+deg: " << components_with_4plusdeg.size() << endl; } int CountCritical() { // F(i, n) { // if(dsu.p[i] == i) { // cout << "found connected component of size " << dsu.sz[i] << endl; // } // } // cout << dsu.components_with_4plusdeg << " " << dsu.components_with_3deg << endl; // cout << _3deg_node_cnt << " " << _4plusdeg_node_cnt << endl; if(dsu.components_with_4plusdeg > 0) { //cout << "case 4+\n"; if(dsu.components_with_4plusdeg == 1 && _4plusdeg_node_cnt == 1) { assert(graphs_without_specific_nodes.size() == 1); // hack for(auto [_, graph_without_the_only_4plusdeg] : graphs_without_specific_nodes) { return info[graph_without_the_only_4plusdeg.excl_node].count_3deg_neighbors() == _3deg_node_cnt && !graph_without_the_only_4plusdeg.has_cycle_flag; } } else { return 0; } } else if(dsu.components_with_3deg > 0) { //cout << "case 3\n"; if(dsu.components_with_3deg == 1 && _3deg_node_cnt <= 4) { int dsu_rep = dsu.find(graphs_without_specific_nodes.begin()->second.excl_node); // hack auto candidates = get_3deg_and_neighbors(dsu_rep); int cnt = 0; for(int cand : candidates) { auto it = graphs_without_specific_nodes.find(cand); assert(it != graphs_without_specific_nodes.end()); assert(it->second.excl_node == cand); //cout << "candidate " << cand << ": " << info[cand].count_3deg_neighbors() << " + " << info[cand].is_3deg() << " == " << _3deg_node_cnt << " with cycle: " << it->second.has_cycle_flag << endl; cnt += info[cand].count_3deg_neighbors() + info[cand].is_3deg() == _3deg_node_cnt && !it->second.has_cycle_flag; } return cnt; } else { return 0; } } else { //cout << "case 2-\n"; if(dsu.components_with_cycles == 0) { return n; } else if(dsu.components_with_cycles == 1) { return dsu.sz[dsu.component_with_cycle]; } else { return 0; } } assert(false); }
#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...