# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
103462 | figter001 | Simurgh (IOI17_simurgh) | C++17 | 3 ms | 384 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],in[nax];
int m;
bool used[nax];
vector<pair<int,int>> g[nax];
int find(int u){
return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
vector<int> ans;
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);
in[a]++;
in[b]++;
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];
if(in[a] != 1){
for(pair<int,int> cur : g[b]){
if(used[cur.second] == 1)
continue;
ans[i] = cur.second;
int r = count_common_roads(ans);
if(r < lst){
ans[i] = id;
break;
}
if(r > lst){
lst = r;
in[a]--;
in[cur.first]++;
used[cur.second] = 1;
break;
}
ans[i] = id;
}
}
if(in[b] != 1){
for(pair<int,int> cur : g[a]){
if(used[cur.second] == 1)
continue;
ans[i] = cur.second;
int r = count_common_roads(ans);
if(r < lst){
ans[i] = id;
break;
}
if(r > lst){
lst = r;
in[b]--;
in[cur.first]++;
used[cur.second] = 1;
break;
}
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... |