| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1100500 | 2024-10-14T06:28:09 Z | MMihalev | Simurgh (IOI17_simurgh) | C++14 | 0 ms | 0 KB |
#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
#include "simurgh.h"
using namespace std;
const int MAX_N=5e2+3;
const int MAX_M=125000;
int n,m;
int q;
vector<int>edges;
vector<pair<int,int>>g[MAX_N];
bool used[MAX_N];
vector<int>comp;
vector<vector<int>>comps;
int adj[MAX_N];
int numedge[MAX_N][MAX_N];
bool stat[MAX_M];
bool checked[MAX_M];
int forsure;
void reset()
{
comps.clear();
edges.clear();
for(int i=0;i<n;i++)
{
adj[i]=-1;
used[i]=0;
}
}
void dfs(int u)
{
if(adj[u]!=-1)
{
if(!checked[adj[u]])
{
comp.push_back(adj[u]);
}
if(stat[adj[u]])forsure=adj[u];
}
used[u]=1;
for(auto [v,edge]:g[u])
{
if(used[v])continue;
edges.push_back(edge);
dfs(v);
}
}
void rep(int prev,int edge)
{
for(int i=0;i<edges.size();i++)
{
if(edges[i]==prev){edges[i]=edge;return;}
}
}
vector<pair<int,int>>s;
int rec(int l,int r,int all)
{
if(l==r)
{
return s[l].first;
}
int mid=(l+r)/2;
int bonus=0;
edges.clear();
for(int i=0;i<n;i++)used[i]=0;
for(int i=l;i<=mid;i++)
{
edges.push_back(s[i].first);
used[s[i].second]=1;
}
for(int i=1;i<n;i++)
{
if(!used[i]){bonus+=stat[numedge[0][i]];edges.push_back(numedge[0][i]);}
}
int cnt=count_common_roads(edges)-bonus;
if(cnt>0)return rec(l,mid);
return rec(mid+1,r);
}
vector<int> find_roads(int N, vector<int> u, vector<int> v)
{
n=N;
m=u.size();
vector<int>ans;
for(int i=0;i<m;i++)
{
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
numedge[u[i]][v[i]]=i;
numedge[v[i]][u[i]]=i;
}
if(n<=240)
{
for(int u=0;u<n;u++)
{
reset();
used[u]=1;
for(auto [v,edge]:g[u])
{
adj[v]=edge;
}
for(auto [v,edge]:g[u])
{
if(!used[v])
{
forsure=-1;
comp.clear();
dfs(v);
if(forsure!=-1)
{
comp.push_back(forsure);
}
comps.push_back(comp);
}
}
for(auto c:comps)
{
edges.push_back(c[0]);
}
for(auto c:comps)
{
int ma=count_common_roads(edges);q++;
vector<int>marked;
marked.push_back(c[0]);
int prev=c[0];
int sega=0;
for(int edge:c)
{
if(edge==c[0])continue;
rep(prev,edge);
int cur=count_common_roads(edges);q++;
if(cur>ma)
{
sega++;
marked.clear();
ma=cur;
marked.push_back(edge);
if(sega==2)break;
}
else if(cur==ma)
{
marked.push_back(edge);
}
prev=edge;
}
for(int edge:marked)stat[edge]=1;
}
for(auto [v,edge]:g[u])checked[edge]=1;
}
}
else
{
for(int u=0;u<n;u++)
{
if(u==0)
{
vector<int>marked;
edges.clear();
for(int v=2;v<n;v++)
{
edges.push_back(numedge[v-1][v]);
}
int ma=-1;
for(auto [v,edge]:g[u])
{
edges.push_back(edge);
int cur=count_common_roads(edges);
if(cur>ma)
{
marked.clear();
marked.push_back(edge);
ma=cur;
}
else if(cur==ma)marked.push_back(edge);
}
for(int edge:marked)stat[edge]=1;
continue;
}
while(1)
{
int bonus=0;
edges.clear();
s.clear();
for(int i=0;i<n;i++)used[i]=0;
for(auto [v,edge]:g[u])
{
if(stat[edge] or v==0)continue;
edges.push_back(edge);
s.push_back({edge,v});
used[v]=1;
}
for(int i=1;i<n;i++)
{
if(!used[i]){bonus+=stat[numedge[0][i]];edges.push_back(numedge[0][i]);}
}
int cur=count_common_roads(edges)-bonus;
if(cur==0)break;
int edge=rec(0,s.size()-1,cur);
stat[edge]=1;
}
}
}
for(int i=0;i<m;i++)
{
if(stat[i])ans.push_back(i);
}
return ans;
}