Submission #1167022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167022		modwwe	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	124 ms	8908 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();
        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];
    void dfs(int x,int y)
    {
        sz[x]=1;
        for(auto f:v[x])
            if(f^y)
            {
                par[f]=x;
                dfs(f,x);
                sz[x]+=sz[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;
            }
        return s5;
    }
  /*  int visit(int x)
    {
        if(can[root][x]==0) assert(0);
        root=x;
        return color[root];
    }*/
    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;
                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