Submission #1167025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167025		modwwe	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	122 ms	9084 KiB

incursion

//#include "richest.h"
//#pragma GCC optimize("Ofast,unroll-loops")
#include "incursion.h"
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1tst"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf=1e18;
const int mod2 = 998244353;
//const int base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en,t,dem1;
ll kk;
ll el = 19;
namespace anna
{
int in[45001];
int sz[45001];
int ou[45001];
vector<int> v[45001];
void dfs(int x,int y)
{
    sz[x]=1;
    in[x]=++dem;
    for(auto f:v[x])
        if(f^y)
        {
            dfs(f,x);
            sz[x]+=sz[f];
        }
    ou[x]=dem;
}
bool check(int x,int y)
{
    if(in[x]<=in[y]&&in[y]<=ou[x])return 1;
    return 0;
}
int center()
{
    dfs(1,0);
    s5=1;
    for(int i=2; i<=n; i++)
        if(sz[i]>n/2)
        {
            if(sz[i]<sz[s5])
                s5=i;
        }
    return s5;
}
vector<int> mark(vector<pair<int,int>>hihi,int safe)
{
    n=hihi.size()+1;
    for(auto x:hihi)
        v[x.first].pb(x.second),
        v[x.second].pb(x.first);
    int x=center();
    dem=0;
    dfs(x,0);
    vector<int> send;
    for(int i=1; i<=n; i++)
        send.pb(check(i,safe));
    return send;
}
};
namespace bruno
{
int sz[45001];
int par[45001];
vector<int> v[45001];
bool go[45001];
int heavy[45001];
void dfs(int x,int y)
{
    sz[x]=1;
    int mxz=0;
    heavy[x]=0;
    for(auto f:v[x])
        if(f^y)
        {
            par[f]=x;
            dfs(f,x);
            sz[x]+=sz[f];
            if(sz[f]>mxz)
                heavy[x]=f;
        }
}
int center()
{
    dfs(1,0);
    s5=1;
    for(int i=2; i<=n; i++)
        if(sz[i]>n/2)
        {
            if(sz[i]<sz[s5])
                s5=i;
        }
        par[s5]=0;
    return s5;
}
void locate(vector<pair<int,int>>hihi,int cur,int t)
{
    n=hihi.size()+1;
    for(auto x:hihi)
        v[x.first].pb(x.second),
        v[x.second].pb(x.first);
    int x=center();
    dfs(x,0);
    while(true)
    {
        go[cur]=1;
        if(t==0)
        {
            cur=par[cur];
            t=visit(cur);
        }
        else
        {
            bool de=0;
            if(!go[heavy[cur]]&&heavy[cur]!=0)
            {
                de=1;
                cur=heavy[cur];
                t=visit(cur);
            }
            else
            {
                for(auto x:v[cur])
                    if(par[x]==cur&&!go[x])
                    {
                        cur=x;
                        t=visit(cur);
                        de=1;
                        break;
                    }
            }
            if(!de) break;
        }
    }
}
};
vector<int> mark(vector<pair<int,int>>nmt,int safe)
{
    return anna::mark(nmt,safe);
}
void locate(vector<pair<int,int>>nmt,int cur,int t)
{
    bruno::locate(nmt,cur,t);
}
/*
void phongbeo()
{
    vector<pair<int,int>>haha;
    haha.pb({1,2});
    haha.pb({2,3});
    can[1][2]=1;
    can[2][1]=1;
    can[2][3]=1;
    can[3][2]=1;
vector<int> kiki=anna::mark(haha,1);
for(int i=0;i<kiki.size();i++)
color[i+1]=kiki[i];
 root=3;
bruno::locate(haha,3,color[3]);;
cout<<root;
}*/

Compilation message (stderr)

incursion.cpp:27:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const int inf=1e18;
      |               ^~~~

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