#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 505
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "simurgh.h"
//#define count_common_roads(vec) IR.common(vec)
struct Interactive
{
int n;
set <int> s;
void Init(int _n)
{
n=_n;
int x;
for(int i=1;i<n;i++) cin>>x,s.insert(x);
}
int common(vector <int> vec)
{
int res=0;
for(int x:vec)
if(s.find(x)!=s.end()) res++;
return res;
}
} IR;
struct DSU
{
int r[N];
void Init(int n)
{
for(int u=1;u<=n;u++) r[u]=u;
}
int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
bool join(int u,int v)
{
if(root(u)==root(v)) return 0;
r[root(u)]=root(v);
return 1;
}
} DS;
int n,m,i,j,u,v,in_MyTree[N*N],in_ZalTree[N*N],num[N][N],p[N],done[N],U[N*N],V[N*N],MyTree_score,h[N],deg[N];
vector <int> MyTree,a[N];
int Score(vector <int> vec)
{
DS.Init(n);
vector <int> NowTree;
for(int x:vec)
{
DS.join(U[x],V[x]);
NowTree.push_back(x);
}
int added_score;
for(int x:MyTree)
if(DS.join(U[x],V[x]))
{
NowTree.push_back(x);
added_score+=in_ZalTree[x];
}
return count_common_roads(NowTree)-added_score;
}
vector <int> MyTree_Replace(int u,int v)
{
vector <int> res;
for(int x:MyTree)
if(x!=u) res.push_back(x);
res.push_back(v);
return res;
}
void DFS(int u)
{
for(int v:a[u])
if(p[v]==0)
{
p[v]=u; h[v]=h[u]+1;
DFS(v);
MyTree.push_back(num[u][v]);
in_MyTree[num[u][v]]=1;
}
}
vector <int> find_roads(int _n,vector <int> _U,vector <int> _V)
{
n=_n; m=_U.size();
for(i=0;i<m;i++) U[i]=_U[i]+1,V[i]=_V[i]+1;
for(i=0;i<m;i++)
{
u=U[i]; v=V[i];
a[u].push_back(v); a[v].push_back(u);
num[u][v]=num[v][u]=i;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Determine MyTree
p[1]=-1;
DFS(1);
MyTree_score=count_common_roads(MyTree);
memset(in_ZalTree,-1,sizeof(in_ZalTree));
for(i=0;i<m;i++)
if(!in_MyTree[i])
{
vector <int> path;
auto Walk=[&](int u,int v)
{
int res=-1;
if(h[u]<h[v]) swap(u,v);
while(h[u]>h[v])
{
if(in_ZalTree[num[u][p[u]]]==-1)
path.push_back(num[u][p[u]]);
else res=num[u][p[u]];
u=p[u];
}
while(u!=v)
{
if(in_ZalTree[num[u][p[u]]]==-1)
path.push_back(num[u][p[u]]);
else res=num[u][p[u]];
u=p[u];
if(in_ZalTree[num[v][p[v]]]==-1)
path.push_back(num[v][p[v]]);
else res=num[v][p[v]];
v=p[v];
}
return res;
};
int determined_edge=Walk(U[i],V[i]);
if(path.size()==0) continue;
if(determined_edge==-1)
{
vector <int> Bigger,Smaller,Equal;
for(int x:path)
{
int k=count_common_roads(MyTree_Replace(x,i));
if(MyTree_score>k)
Bigger.push_back(x);
else if(MyTree_score<k)
Smaller.push_back(x);
else Equal.push_back(x);
}
if(Bigger.size()>0)
{
for(int x:Bigger) in_ZalTree[x]=1;
for(int x:Equal) in_ZalTree[x]=0;
}
else if(Smaller.size()>0)
{
for(int x:Smaller) in_ZalTree[x]=0;
for(int x:Equal) in_ZalTree[x]=1;
}
else
for(int x:Equal) in_ZalTree[x]=0;
}
else
{
int k=count_common_roads(MyTree_Replace(determined_edge,i));
int i_score=in_ZalTree[determined_edge];
if(k>MyTree_score) i_score++;
if(k<MyTree_score) i_score--;
for(int x:path)
{
int k=count_common_roads(MyTree_Replace(x,i));
in_ZalTree[x]=i_score;
if(MyTree_score>k) in_ZalTree[x]++;
if(MyTree_score<k) in_ZalTree[x]--;
}
}
}
for(int x:MyTree)
if(in_ZalTree[x]==-1) in_ZalTree[x]=1;
//////////////////////////////////////////////////////////////////////////////////////////////////
//Determine ZalTree
queue <int> q;
for(u=1;u<=n;u++)
{
vector <int> vec;
for(int v:a[u]) vec.push_back(num[u][v]);
deg[u]=Score(vec);
if(deg[u]==1) q.push(u);
}
vector <int> res;
for(i=1;i<n;i++)
{
int u=q.front(); q.pop();
done[u]=1;
vector <int> candidate;
for(int v:a[u])
if(done[v]==0)
candidate.push_back(num[u][v]);
int l=0,r=candidate.size()-1;
while(l<r)
{
int mid=(l+r)>>1;
vector <int> vec;
for(j=0;j<=mid;j++) vec.push_back(candidate[j]);
if(Score(vec)>0) r=mid; else l=mid+1;
}
int x=candidate[l];
res.push_back(x);
if(U[x]==u) v=V[x]; else v=U[x];
deg[v]--;
if(deg[v]==1) q.push(v);
}
return res;
}
/*
int main()
{
freopen("simurgh.inp","r",stdin);
freopen("simurgh.out","w",stdout);
int n,k,u,v;
cin>>n;
IR.Init(n);
vector <int> U,V;
while(cin>>u>>v) U.push_back(u),V.push_back(v);
vector <int> vec=find_roads(n,U,V);
for(int x:vec) cout<<x<<" ";
}
*/
Compilation message
simurgh.cpp: In function 'int Score(std::vector<int>)':
simurgh.cpp:76:40: warning: 'added_score' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | return count_common_roads(NowTree)-added_score;
| ^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
