| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 831701 |
2023-08-20T12:27:35 Z |
Antekb |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
468 KB |
#include<bits/stdc++.h>
#include "simurgh.h"
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using ll = long long;
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
const int N=505;
int r[N], vis[N], par[N], paredg[N], dep[N];
int dobry[N];
int deg[N];
vii E[N];
vii edg;
int n;
int find(int v){
if(r[v]==v)return v;
return r[v]=find(r[v]);
}
void Union(int u, int v){
r[find(u)]=find(v);
}
void dfs(int v){
vis[v]=1;
for(auto ee:E[v]){
int u=ee.st, e=ee.nd;
//deb(v, u);
if(!vis[u]){
paredg[u]=e;
par[u]=v;
dep[u]=dep[v]+1;
dfs(u);
}
}
}
vii drz;
int licz(vi V){
for(int i=0; i<n; i++){
r[i]=i;
}
vi V2;
int sum=0;
for(int i:V){
V2.pb(i);
Union(edg[i].st, edg[i].nd);
}
for(pii i:drz){
if(find(edg[i.st].st)!=find(edg[i.st].nd)){
sum+=i.nd;
V2.pb(i.st);
Union(edg[i.st].st, edg[i.st].nd);
}
}
int ile=count_common_roads(V2);
return ile-sum;
}
std::vector<int> find_roads(int _n, std::vector<int> _u, std::vector<int> _v) {
n=_n;
for(int i=0; i<_u.size(); i++)
{
E[_u[i]].eb(_v[i], i);
E[_v[i]].eb(_u[i], i);
edg.eb(_u[i], _v[i]);
}
par[0]=paredg[0]=-1;
dfs(0);
vi V;
for(int i=1; i<n; i++){
deb(i, par[i], paredg[i], dep[i]);
V.pb(paredg[i]);
}
int ile=count_common_roads(V);
for(int v=0; v<n; v++){
for(pii ee:E[v]){
int u=ee.st, e=ee.nd;
if(dep[u]>dep[v] && v!=par[u]){
vi todo;
while(true){
int uu=find(u);
if(uu==find(v)){
break;
}
else{
int e2=paredg[uu];
for(int &i:V){
if(i==e2)i=e;
}
int ile2=count_common_roads(V);
if(ile2==ile){
todo.pb(e2);
}
else if(ile2>ile){
//kraw=e;
}
else{
dobry[uu]=1;
//kraw=e2;
}
r[uu]=par[uu];
for(int &i:V){
if(i==e)i=e2;
}
}
}
for(int uu=u; uu!=v; uu=par[uu]){
bool czy=0;
for(int i:todo){
if(i==paredg[uu]){
czy=1;
break;
}
}
if(czy)continue;
int e2=paredg[uu];
for(int &i:V){
if(i==e2)i=e;
}
int ile2=count_common_roads(V);
if(ile2+dobry[u]>ile){
for(int i:todo){
if(i==paredg[edg[i].st])dobry[edg[i].st]=1;
else dobry[edg[i].nd]=1;
}
}
for(int &i:V){
if(i==e)i=e2;
}
break;
}
}
}
}
for(int i=1; i<n; i++){
drz.eb(paredg[i], dobry[i]);
}
for(int i=0; i<n; i++){
vis[i]=0;
vi V2;
for(auto e:E[i]){
V2.pb(e.nd);
}
deg[i]=licz(V2);
}
vi ans;
for(int ii=1; ii<n; ii++){
int v=-1;
for(int i=0; i<n; i++){
if(!vis[i] && deg[i]==1){
v=i;
}
}
vi V2;
assert(v!=-1);
for(auto e:E[v]){
if(!vis[e.st])V2.pb(e.nd);
}
int l=0, r=V2.size()-1;
while(l<r){
int m=(l+r)>>1;
vi V3=V2;
V3.resize(m+1);
if(licz(V3)==0)l=m+1;
else r=m;
}
ans.pb(V2[l]);
int u=edg[ans.back()].st^edg[ans.back()].nd^v;
deg[u]--;
deg[v]--;
vis[v]=1;
}
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0; i<_u.size(); i++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
320 KB |
correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
