#include <vector>
#include "incursion.h"
#include <cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;
using vintp = vector<intp>;
const int MAX_N=45010;
int n;
vintp eg[MAX_N];
int sz[MAX_N];
vint val;
int isleaf=0;
bool compe(const intp &e1,const intp &e2)
{
return e1.second>e2.second;
}
int fillsz(int v,int p)
{
sz[v]=1;
for(auto &e : eg[v])
if(e.first!=p)
{
e.second=fillsz(e.first,v);
sz[v]+=e.second;
}
for(auto &e : eg[v])
if(e.first==p)
e.second=n-sz[v];
sort(eg[v].begin(),eg[v].end(),compe);
return sz[v];
}
bool ismid(int v)
{
int mx=0;
for(auto e : eg[v])
mx=max(mx,e.second);
int c=0;
for(auto e : eg[v])
if(e.second==mx)c++;
return c>=2;
}
void dfs(int v,int p)
{
if(ismid(v))
{
val[v-1]=isleaf;
}
else if(p==0)
{
val[v-1]=0;
}
else
{
int mx=0;
for(auto e : eg[v])
mx=max(mx,e.second);
for(auto e : eg[v])
if(e.first==p)
val[v-1]=(e.second==mx);
}
for(auto e : eg[v])
if(e.first!=p)
dfs(e.first,v);
}
vint mark(vintp F, int safe)
{
n=F.size()+1;
for(int i=1;i<=n;i++)
eg[i].clear();
for(int i=0;i<n-1;i++)
{
int u=F[i].first,v=F[i].second;
eg[u].push_back({v,0});
eg[v].push_back({u,0});
}
val.resize(n);
fillsz(safe,0);
isleaf=(eg[safe].size()<=1);
dfs(safe,0);
return val;
}
bool checkleaf(int v,int p)
{
if(isleaf==-1)return false;
int flag=1;
for(auto e : eg[v])
if(e.first!=p && eg[e.first].size()>1)flag=0;
if(flag==0)return false;
if(isleaf==0)return true;
for(auto e : eg[v])
if(e.first!=p)
{
if(visit(e.first)==0)return true;
visit(v);
}
return false;
}
void calc(int v,int p,int t)
{
if(ismid(v))
{
isleaf=t;
if(checkleaf(v,p))
return;
for(auto e : eg[v])
if(e.first!=p)
{
int nt=visit(e.first);
if(nt==0)
{
calc(e.first,v,nt);
return;
}
visit(v);
}
return;
}
if(checkleaf(v,p))
return;
if(t==1)return calc(eg[v][0].first,v,visit(eg[v][0].first));
if(t==0 && eg[v].size()<=1)return;
int nt;
if(eg[v][1].first!=p)
{
nt=visit(eg[v][1].first);
if(nt==0)
{
calc(eg[v][1].first,v,nt);
return;
}
visit(v);
}
nt=visit(eg[v][2].first);
if(nt==0)
{
calc(eg[v][2].first,v,nt);
return;
}
visit(v);
}
void locate(vintp F, int curr, int t)
{
cout << curr << ' ';
n=F.size()+1;
for(int i=1;i<=n;i++)
eg[i].clear();
for(int i=0;i<n-1;i++)
{
int u=F[i].first,v=F[i].second;
eg[u].push_back({v,0});
eg[v].push_back({u,0});
}
fillsz(curr,0);
isleaf=-1;
calc(curr,0,t);
return;
}
Compilation message
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | int l = (numbers.size() == N ? N : 0);
| ~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2820 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
12932 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
8788 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2820 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
