Submission #1048540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048540		ibm2006	The Ties That Guide Us (CEOI23_incursion)	C++17	60 / 100	227 ms	77972 KiB

incursion

#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],par[1100000],c[1100000],h[1100000],siz[1100000],realcurr,realt,safe;
vector<ll> v[1100000],u;
pair<ll,pair<ll,ll>> p;
void Clear()
{
    ll i;
    u.clear();
    for(i=1;i<=n;i++)
    {
        v[i].clear();
        siz[i]=0;
        par[i]=0;
        h[i]=0;
        c[i]=0;
    }
}
void get_siz(ll x,ll y)
{
    ll i;
    siz[x]=1;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        get_siz(v[x][i],x);
        siz[x]+=siz[v[x][i]];
    }
}
ll centroid(ll x,ll y,ll z)
{
    ll i;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        if(siz[v[x][i]]*2>n)
            return centroid(v[x][i],x,z);
    }
    return x;
}
ll dfs(ll x,ll y)
{
    if(x==t)
    {
        u[x-1]=1;
        return 1;
    }
    if(x==0)
        return 0;
    ll i;
    c[x]=1;
    for(i=0;i<h[x];i++)
    {
        if(c[v[x][i]])
            continue;
        if(dfs(v[x][i],x))
        {
            u[x-1]=1;
            return 1;
        }
    }
    return 0;
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
n=F.size()+1;
Clear();
t=safe;
for(i=0;i<n-1;i++)
{
    x=F[i].first;
    y=F[i].second;
    v[x].push_back(y);
    v[y].push_back(x);
    h[x]++;
    h[y]++;
}
get_siz(1,0);
x=centroid(1,0,siz[1]);
get_siz(x,0);
y=0;
for(i=0;i<v[x].size();i++)
{
    y=v[x][i];
    if((n-siz[y])*2<=n)
    {
        break;
    }
    y=0;
}
c[x]=1;
c[y]=1;
u.resize(n);
dfs(x,0);
dfs(y,0);
return u;
}
ll ask(ll x)
{
    if(x==0)
        return 0;
    if(realcurr==x)
    {
        return realt;
    }
    realcurr=x;
    realt=visit(x);
    return realt;
}
void f(ll x,ll y)
{
    par[x]=y;
    ll i;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y||c[v[x][i]])
            continue;
        f(v[x][i],x);
    }
}
pair<ll,pair<ll,ll>> get_child(ll x)
{
    ll i;
    pair<ll,pair<ll,ll>> p={0,{0,0}};
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==par[x]||c[v[x][i]])
            continue;
        if(p.first==0)
            p.first=v[x][i];
        else if(p.second.first==0)
            p.second.first=v[x][i];
            else
                p.second.second=v[x][i];
    }
    return p;
}
ll subtree(ll x,ll y,ll z)
{
    if(x==z)
        return 1;
    ll i;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y||c[v[x][i]])
            continue;
        if(subtree(v[x][i],x,z))
            return 1;
    }
    return 0;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
n=F.size()+1;
Clear();
realcurr=curr;
realt=t;
for(i=0;i<n-1;i++)
{
    x=F[i].first;
    y=F[i].second;
    v[x].push_back(y);
    v[y].push_back(x);
    h[x]++;
    h[y]++;
}
get_siz(1,0);
x=centroid(1,0,siz[1]);
get_siz(x,0);
y=0;
for(i=0;i<v[x].size();i++)
{
    y=v[x][i];
    if((n-siz[y])*2<=n)
    {
        break;
    }
    y=0;
}
c[x]=1;
c[y]=1;
f(x,0);
f(y,0);
if(subtree(y,0,curr))
{
    swap(x,y);
}
while(!t)
{
    if(curr==x)
    {
        break;
    }
    curr=par[curr];
    t=visit(curr);
}
if(t==0)
    {curr=y;
    swap(x,y);
    t=visit(x);
    }
get_siz(x,0);
while(1)
{
    p=get_child(curr);
    if(siz[p.first]<siz[p.second.first])
        swap(p.first,p.second.first);
    if(siz[p.first]<siz[p.second.second])
        swap(p.first,p.second.second);
    if(siz[p.second.first]<siz[p.second.second])
        swap(p.second.first,p.second.second);
    t=ask(p.first);
    if(t==1)
    {
        curr=p.first;
        continue;
    }
    t=ask(curr);
    t=ask(p.second.first);
    if(t==1)
    {
        curr=p.second.first;
        continue;
    }
    t=ask(curr);
    t=ask(p.second.second);
    if(t==1)
    {
        curr=p.second.second;
        continue;
    }
    t=ask(curr);
    break;
}
return;
}

Compilation message (stderr)

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:85:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 | for(i=0;i<v[x].size();i++)
      |         ~^~~~~~~~~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:173:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 | for(i=0;i<v[x].size();i++)
      |         ~^~~~~~~~~~~~
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);
      |                  ~~~~~~~~~~~~~~~^~~~

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40