| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 684118 |
2023-01-20T12:36:34 Z |
79brue |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
596 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct unionFind{
int par[502];
void init(int n){
for(int i=0; i<n; i++) par[i] = i;
}
int find(int x){
if(par[x] == x) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[y] = x;
}
};
struct Edge{
int s, e, idx;
Edge(){}
Edge(int s, int e, int idx): s(s), e(e), idx(idx){}
};
struct Comparison{
int a, b, v; /// ans[a] - ans[b] = v
Comparison(){}
Comparison(int a, int b, int v): a(a), b(b), v(v){}
bool operator<(const Comparison &r)const{
return abs(v) > abs(r.v);
}
};
int n, m;
vector<Edge> link[502];
int edgeIdx[502][502];
int ex[150002], ey[150002];
bool ans[150002];
void oneTree();
void everyEdge();
vector<int> find_roads(int N, vector<int> u, std::vector<int> v) {
n = N, m = (int)u.size();
for(int i=0; i<n; i++) for(int j=0; j<n; j++) edgeIdx[i][j] = -1;
for(int i=0; i<m; i++){
link[u[i]].push_back(Edge(u[i], v[i], i));
link[v[i]].push_back(Edge(v[i], u[i], i));
ex[i] = u[i], ey[i] = v[i];
edgeIdx[ex[i]][ey[i]] = i;
edgeIdx[ey[i]][ex[i]] = i;
}
oneTree();
everyEdge();
vector<int> ret;
for(int i=0; i<m; i++) if(ans[i]) ret.push_back(i);
return ret;
}
vector<Edge> treeLink[502];
vector<int> treeEdges;
bool inTree[150002];
int depth[502], par[502], LCADB[502][10];
bool checked[150002];
void dfs_tree(int x, int p){
par[x] = p;
for(Edge y: treeLink[x]){
if(y.e == p) continue;
depth[y.e] = depth[x] + 1;
dfs_tree(y.e, x);
}
}
int getLCA(int x, int y){
if(depth[x] > depth[y]) swap(x, y);
for(int d=9; d>=0; d--) if((depth[y] - depth[x]) & (1<<d)) y = LCADB[y][d];
if(x==y) return x;
for(int d=9; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
return par[x];
}
void apply(int x, int t){
if(checked[x] && ans[x] != t) exit(1);
checked[x] = 1, ans[x] = t;
}
void oneTree(){
/// 아무 트리나 만들기
unionFind dsu;
dsu.init(n);
for(int i=0; i<m; i++){
if(dsu.find(ex[i]) != dsu.find(ey[i])){
dsu.merge(ex[i], ey[i]);
inTree[i] = 1;
treeLink[ex[i]].push_back(Edge(ex[i], ey[i], i));
treeLink[ey[i]].push_back(Edge(ey[i], ex[i], i));
treeEdges.push_back(i);
}
}
int treeSum = count_common_roads(treeEdges);
/// 트리를 탐색하기
dfs_tree(0, -1);
for(int i=0; i<n; i++) LCADB[i][0] = par[i];
for(int d=1; d<10; d++) for(int i=0; i<n; i++) LCADB[i][d] = (LCADB[i][d-1] == -1 ? -1 : LCADB[LCADB[i][d-1]][d-1]);
/// 각 간선이 포함되는지 확인하기
vector<Comparison> compare;
for(int edge: treeEdges){
int u = ex[edge], v = ey[edge];
if(depth[u] > depth[v]) swap(u, v);
/// 위로 가는 간선이 있는지 보자
int up = -1;
for(int i=0; i<m; i++){
if(inTree[i]) continue;
if((getLCA(v, ex[i]) == v) == (getLCA(v, ey[i]) == v)) continue;
up = i;
break;
}
if(up == -1){
checked[edge] = 1;
ans[edge] = 1;
continue;
}
/// 쿼리를 날려 확인해 보자
vector<int> qv1 = treeEdges;
qv1.erase(find(qv1.begin(), qv1.end(), edge));
qv1.push_back(up);
int qa1 = count_common_roads(qv1);
compare.push_back(Comparison(edge, up, treeSum - qa1));
/// 이제 쿼리를 하나 더 날리자
int top = getLCA(ex[up], ey[up]);
int highest;
if(top == ex[up]){
if(v != ey[up]) highest = edgeIdx[ey[up]][par[ey[up]]];
else highest = edgeIdx[par[ey[up]]][par[par[ey[up]]]];
}
else if(top == ey[up]){
if(v != ex[up]) highest = edgeIdx[ex[up]][par[ex[up]]];
else highest = edgeIdx[par[ex[up]]][par[par[ex[up]]]];
}
else if(v != ex[up]) highest = edgeIdx[ex[up]][par[ex[up]]];
else if(v != ey[up]) highest = edgeIdx[ey[up]][par[ey[up]]];
else exit(1);
vector<int> qv2 = qv1;
qv2.erase(find(qv2.begin(), qv2.end(), highest));
qv2.push_back(edge);
int qa2 = count_common_roads(qv2);
compare.push_back(Comparison(highest, edge, qa1 - qa2));
}
/// 비교 데이터를 바탕으로 결정하자.
sort(compare.begin(), compare.end());
for(Comparison com: compare){
if(com.v){
if(com.v == 1) apply(com.a, 1), apply(com.b, 0);
else apply(com.b, 1), apply(com.a, 0);
}
else if(checked[com.a] || checked[com.b]){
assert(!checked[com.a] || !checked[com.b] || ans[com.a] == ans[com.b]);
int result = ans[com.a] || ans[com.b];
apply(com.a, result), apply(com.b, result);
}
}
for(int edge: treeEdges){
assert(checked[edge]);
}
}
void dnc(vector<int> &edgeList){
if(edgeList.empty()) return;
vector<int> qv;
unionFind dsu;
dsu.init(n);
for(auto x: edgeList){
qv.push_back(x);
dsu.merge(ex[x], ey[x]);
}
int base = 0;
for(auto x: treeEdges){
if(dsu.find(ex[x]) == dsu.find(ey[x])) continue;
base += ans[x];
qv.push_back(x);
dsu.merge(ex[x], ey[x]);
}
int value = count_common_roads(qv) - base;
if(!value) return;
if((int)edgeList.size() == 1){
apply(edgeList[0], 1);
return;
}
vector<int> list1, list2;
int m = (int)edgeList.size() / 2;
for(int i=0; i<(int)edgeList.size(); i++){
if(i < m) list1.push_back(edgeList[i]);
else list2.push_back(edgeList[i]);
}
dnc(list1);
dnc(list2);
}
void everyEdge(){
for(int i=0; i<n; i++){
/// 정점 i 주변의 간선들을 찾을 것이다.
vector<int> searchTo;
for(Edge e: link[i]) if(!inTree[e.idx]) searchTo.push_back(e.idx);
dnc(searchTo);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
