#include "simurgh.h"
#include <cassert>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>
class Dsu{
public:
std::vector<int> mult;
Dsu(int n) {
mult.resize(n);
for(int i = 0; i < n; i++)
mult[i] = i;
}
int jump(int gala) {
if(gala != mult[gala])
mult[gala] = jump(mult[gala]);
return mult[gala];
}
bool connect(int gala, int galb) {
return jump(gala) == jump(galb);
}
void unite(int gala, int galb) {
gala = jump(gala);
galb = jump(galb);
if(gala == galb)
return ;
mult[gala] = galb;
}
};
std::vector<std::pair<int,int>> edges;
std::vector<int> get_skeleton(int n) {
Dsu dsu(n);
std::vector<int> skeleton;
for(int i = 0; i < edges.size(); i++) {
int x = edges[i].first;
int y = edges[i].second;
if(dsu.connect(x, y) == 0) {
dsu.unite(x, y);
skeleton.push_back(i);
}
}
return skeleton;
}
std::vector<int> level, far, state;
std::vector<std::vector<int>> g;
void dfs(int node, int parent) {
for(int h = 0; h < g[node].size(); h++) {
int id = g[node][h];
int to = edges[id].first + edges[id].second - node;
if(to != parent) {
level[to] = level[node] + 1;
far[to] = id;
dfs(to, node);
}
}
}
void mark_skeleton(std::vector<int> &skeleton, int n) {
g.resize(n);
for(int i = 0; i < skeleton.size(); i++) {
int id = skeleton[i];
g[edges[id].first].push_back(id);
g[edges[id].second].push_back(id);
}
dfs(0, -1);
}
std::vector<int> with(std::vector<int> base, int val) {
base.push_back(val);
return base;
}
std::vector<int> without(std::vector<int> base, int val) {
base.erase(std::find(base.begin(), base.end(), val));
return base;
}
std::vector<int> exchange(std::vector<int> base, int val, int val2) {
for(int i = 0; i < base.size(); i++)
if(base[i] == val)
base[i] = val2;
return base;
}
void update(std::vector<int> &skeleton, int id) {
int x = edges[id].first, y = edges[id].second;
std::vector<int> path;
if(level[x] < level[y])
std::swap(x, y);
while(level[x] != level[y]) {
path.push_back(far[x]);
x = edges[far[x]].first + edges[far[x]].second - x;
}
while(x != y) {
path.push_back(far[x]);
x = edges[far[x]].first + edges[far[x]].second - x;
path.push_back(far[y]);
y = edges[far[y]].first + edges[far[y]].second - y;
}
bool chance = 0;
for(int i = 0; i < path.size(); i++) {
int id2 = path[i];
if(state[id2] == 0)
chance = 1;
}
if(chance == 0)
return ;
int base = count_common_roads(skeleton);
for(int i = 0; i < path.size(); i++) {
int id2 = path[i];
if(0 < state[id2])
state[id] = state[id2] - base + count_common_roads(exchange(skeleton, id2, id));
}
if(0 < state[id]) {
for(int i = 0; i < path.size(); i++) {
int id2 = path[i];
if(0 == state[id2])
state[id2] = state[id] + count_common_roads(exchange(skeleton, id2, id)) - base;
}
} else {
std::vector<int> eval(path.size());
int smax = base;
for(int i = 0; i < path.size(); i++) {
int id2 = path[i];
eval[i] = count_common_roads(exchange(skeleton, id2, id));
smax = std::max(eval[i], smax);
}
for(int i = 0; i < path.size(); i++)
if(smax == eval[i])
state[path[i]] = 1;
else
state[path[i]] = 2;
}
}
int eval(std::vector<int> aux, std::vector<int> &skeleton, int n){
Dsu dsu(n);
for(int i = 0; i < aux.size(); i++)
dsu.unite(edges[aux[i]].first, edges[aux[i]].second);
int cost = 0;
for(int i = 0; i < skeleton.size(); i++) {
int id = skeleton[i];
if(dsu.connect(edges[id].first, edges[id].second) == 0) {
dsu.unite(edges[id].first, edges[id].second);
aux.push_back(id);
cost += state[id] - 1;
}
}
return count_common_roads(aux) - cost;
}
std::vector<int> first_k(std::vector<int> aux, int k) {
std::vector<int> result;
for(int i = 0; i < k; i++)
result.push_back(aux[i]);
return result;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
edges.resize(u.size());
state.resize(u.size());
far.resize(n);
level.resize(n);
for(int i = 0;i < edges.size(); i++)
edges[i] = {u[i], v[i]};
std::vector<int> skeleton = get_skeleton(n);
mark_skeleton(skeleton, n);
for(int i = 0; i < edges.size(); i++)
if(std::find(skeleton.begin(), skeleton.end(), i) == skeleton.end())
update(skeleton, i);
for(int i = 0; i < skeleton.size(); i++)
if(state[skeleton[i]] == 0)
state[skeleton[i]] = 2;
std::vector<std::vector<int>> ad(n);
for(int i = 0; i < u.size(); i++) {
if(0 < state[i])
continue;
if(u[i] < v[i])
ad[u[i]].push_back(i);
else
ad[v[i]].push_back(i);
}
for(int i = 0; i < n; i++) {
int total = eval(ad[i], skeleton, n);
for(int j = 0; j < total; j++) {
int x = 0;
for(int jump = (1 << 10); 0 < jump; jump /= 2) {
if(x + jump <= ad[i].size() && eval(first_k(ad[i], x + jump), skeleton, n) <= j)
x += jump;
}
state[ad[i][x]] = 2;
}
}
std::vector<int> sol;
for(int i = 0; i < u.size(); i++)
if(state[i] == 2)
sol.push_back(i);
return sol;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> get_skeleton(int)':
simurgh.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int h = 0; h < g[node].size(); h++) {
| ~~^~~~~~~~~~~~~~~~
simurgh.cpp: In function 'void mark_skeleton(std::vector<int>&, int)':
simurgh.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i = 0; i < skeleton.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> exchange(std::vector<int>, int, int)':
simurgh.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0; i < base.size(); i++)
| ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'void update(std::vector<int>&, int)':
simurgh.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
simurgh.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
simurgh.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
simurgh.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
simurgh.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i = 0; i < path.size(); i++)
| ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'int eval(std::vector<int>, std::vector<int>&, int)':
simurgh.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int i = 0; i < aux.size(); i++)
| ~~^~~~~~~~~~~~
simurgh.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i = 0; i < skeleton.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:171:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for(int i = 0;i < edges.size(); i++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:176:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for(int i = 0; i < edges.size(); i++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:180:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i = 0; i < skeleton.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
simurgh.cpp:185:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | for(int i = 0; i < u.size(); i++) {
| ~~^~~~~~~~~~
simurgh.cpp:199:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | if(x + jump <= ad[i].size() && eval(first_k(ad[i], x + jump), skeleton, n) <= j)
| ~~~~~~~~~^~~~~~~~~~~~~~~
simurgh.cpp:206:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for(int i = 0; i < u.size(); i++)
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
correct |
| 2 |
Correct |
1 ms |
256 KB |
correct |
| 3 |
Incorrect |
264 ms |
3688 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
