| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 407411 |
2021-05-18T22:16:06 Z |
peuch |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
332 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
int n, m;
vector<int> u, v;
vector<int> ar[MAXN], id[MAXN];
int marc[MAXN], pai[MAXN], paiID[MAXN], prof[MAXN];
int grp[200000];
int pode[200000];
int cnt[200000];
int a;
int rep[MAXN], tam[MAXN];
vector<int> getPath(int a, int b);
vector<int> getST(vector<int> base);
bool uni(int a, int b);
int find(int a);
void dfs(int cur);
vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
n = _n;
u = _u, v = _v;
m = u.size();
for(int i = 0; i < u.size(); i++){
ar[u[i]].push_back(v[i]);
id[u[i]].push_back(i);
ar[v[i]].push_back(u[i]);
id[v[i]].push_back(i);
}
vector<int> nulo;
vector<int> tree = getST(nulo);
a = count_common_roads(tree);
for(int i = 0; i < tree.size(); i++)
pode[tree[i]] = 1;
dfs(0);
for(int i = 0; i < m; i++){
if(grp[i] != 0 || pode[i]) continue;
vector<int> path = getPath(u[i], v[i]);
// printf("Current cycle: %d\nPath: ", i);
// for(int j = 0; j < path.size(); j++)
// printf("%d ", path[j]);
// printf("\n");
int maxi = 0;
bool flag = false;
tree.push_back(i);
cnt[i] = a;
for(int j = 0; j < path.size(); j++){
if(grp[path[j]] != 0){
if(flag) continue;
if(grp[path[j]] == 1) continue;
flag = true;
}
vector<int> test;
for(int k = 0; k < tree.size(); k++)
if(tree[k] != path[j]) test.push_back(tree[k]);
// printf("\tTesting: %d\n", path[j]);
cnt[path[j]] = count_common_roads(test);
maxi = max(maxi, cnt[path[j]]);
}
path.push_back(i);
for(int j = 0; j < path.size(); j++){
if(grp[path[j]] != 0) continue;
if(cnt[path[j]] == maxi) grp[path[j]] = -1;
if(cnt[path[j]] != maxi) grp[path[j]] = 1;
// printf("Cnt[%d] = %d -> grp = %d\n", path[j], cnt[path[j]], grp[path[j]]);
}
tree.pop_back();
}
vector<int> ans;
for(int i = 0; i < m; i++)
if(grp[i] != -1) ans.push_back(i);
// for(int i = 0; i < ans.size(); i++){
// printf("%d ", ans[i]);
// }
// printf("\n");
return ans;
}
vector<int> getPath(int a, int b){
vector<int> ret;
if(prof[a] < prof[b]) swap(a, b);
while(prof[a] > prof[b]){
ret.push_back(paiID[a]);
a = pai[a];
}
while(a != b){
ret.push_back(paiID[a]);
a = pai[a];
ret.push_back(paiID[b]);
b = pai[b];
}
return ret;
}
vector<int> getST(vector<int> base){
vector<int> ret;
for(int i = 0; i < n; i++){
tam[i] = 1;
rep[i] = i;
}
for(int i = 0; i < base.size(); i++)
uni(u[base[i]], v[base[i]]);
for(int i = 0; i < m; i++)
if(uni(u[i], v[i])) ret.push_back(i);
return ret;
}
bool uni(int a, int b){
a = find(a);
b = find(b);
if(a == b) return 0;
if(tam[a] < tam[b]) swap(a, b);
tam[a] += tam[b];
rep[b] = a;
return 1;
}
int find(int a){
if(a == rep[a]) return a;
return rep[a] = find(rep[a]);
}
void dfs(int cur){
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(!pode[id[cur][i]]) continue;
if(viz == pai[cur]) continue;
pai[viz] = cur;
paiID[viz] = id[cur][i];
prof[viz] = prof[cur] + 1;
dfs(viz);
}
}
/*
5 7
0 1
1 2
2 3
3 4
0 2
1 3
4 2
1 3 4 6
*/
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < u.size(); i++){
| ~~^~~~~~~~~~
simurgh.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < tree.size(); i++)
| ~~^~~~~~~~~~~~~
simurgh.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int j = 0; j < path.size(); j++){
| ~~^~~~~~~~~~~~~
simurgh.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int k = 0; k < tree.size(); k++)
| ~~^~~~~~~~~~~~~
simurgh.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j = 0; j < path.size(); j++){
| ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> getST(std::vector<int>)':
simurgh.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i = 0; i < base.size(); i++)
| ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:145:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i = 0; i < ar[cur].size(); i++){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Correct |
1 ms |
332 KB |
correct |
| 5 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Correct |
1 ms |
332 KB |
correct |
| 5 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Correct |
1 ms |
332 KB |
correct |
| 5 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Correct |
1 ms |
332 KB |
correct |
| 5 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
