# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
103474 | figter001 | Simurgh (IOI17_simurgh) | C++17 | 20 ms | 4768 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 250;
int dsu[nax];
int m,n;
bool used[nax];
vector<pair<int,int>> g[nax];
vector<int> u,v;
int find(int u){
return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}
bool good(vector<int> ans){
for(int i=0;i<n;i++)
dsu[i] = i;
for(int i=0;i<ans.size();i++){
int id = ans[i];
int a = u[id];
int b = v[id];
if(find(a) == find(b))
continue;
dsu[find(b)] = find(a);
}
for(int i=0;i<n;i++)
if(find(i) != find(0))
return 0;
return 1;
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
vector<int> ans;
u = U;
v = V;
n = N;
m = u.size();
for(int i=0;i<n;i++)
dsu[i] = i;
int lst;
for(int i=0;i<m;i++){
int a = u[i];
int b = v[i];
g[a].push_back({b,i});
g[b].push_back({a,i});
if(find(a) == find(b))
continue;
used[i] = 1;
ans.push_back(i);
dsu[find(b)] = find(a);
}
lst = count_common_roads(ans);
for(int i=0;i<ans.size();i++){
int id = ans[i];
int a = u[id];
int b = v[id];
for(int j=0;j<m;j++){
if(used[j])
continue;
ans[i] = j;
if(good(ans) == 1){
int r = count_common_roads(ans);
if(r < lst){
ans[i] = id;
break;
}
if(r > lst){
lst = r;
used[j] = 1;
used[id] = 0;
break;
}
}else
ans[i] = id;
}
}
// for(int i : ans)
// printf("%d ", i);
// printf("\n");
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |