Submission #1167065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167065		modwwe	The Ties That Guide Us (CEOI23_incursion)	C++20	30 / 100	160 ms	9088 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;
/*int cdjt[10001];
namespace sample_grader
{

using std::cout;
using std::cin;
using std::endl;
using std::function;
using std::make_pair;
using std::max;
using std::min;
using std::pair;
using std::swap;
using std::vector;

constexpr int tieLimit = 1000000000;
int N;
int dest;
int curr;
vector<int> T;
vector<pair<int, int>> F;
enum { MARK, LOCATE } phase;

[[noreturn]] void die(const char *const s)
{
    cout << s << endl;
    exit(0);
}

void print_vector(vector<int> v)
{
    cout << "{";
    for (size_t i = 0; i < v.size(); ++i)
    {
        cout <<  v[i];
        if (i + 1 != v.size()) cout << ", ";
    }
    cout << "}";
}

void print_vector(vector<pair<int, int>> v)
{
    cout << "{";
    for (size_t i = 0; i < v.size(); ++i)
    {
        cout << "{" << v[i].first << ", " << v[i].second << "}";
        if (i + 1 != v.size()) cout << ", ";
    }
    cout << "}";
}

} // namespace sample_grader

int visit(int v)
{
    using namespace sample_grader;
    function<void()> die_invalid_call_to_visit = [&]()
    {
        cout << "visit(" << v << ")" << endl;
        die("Invalid call to visit");
    };
    if (phase == MARK || v < 1 || v > N) die_invalid_call_to_visit();

    bool adjacent = false;
    /*   for (auto e : F)
       {
           if (e == make_pair(v, curr) or e == make_pair(curr, v))
           {
               adjacent = true;
           }
       }
       if (not adjacent) die_invalid_call_to_visit();
    curr = v;
    cout << "visit(" << v << ") returned " << T[v - 1] << endl;
    return T[cdjt[v] - 1];
}*/
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);
        if(n%2==0)
    {
        s2=-1;
        for(auto f:v[x])
            if(sz[f]==n/2)
                s2=f;
        if(s2!=-1)
            dfs(s2,x);
    }
    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);
        if(n%2==0)
    {
        s2=-1;
        for(auto f:v[x])
        if(sz[f]==n/2)
        s2=f;
    if(s2!=-1)
  heavy[x]=0,par[x]=s2;
    }
    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);
}/*
int main()
{
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    using namespace sample_grader;
    if (!(cin >> N >> dest) or N < 2 or dest < 1 or dest > N) die("Invalid input");

    vector<int> deg(N + 1);
    for(int i = 1; i < N; ++i)
    {
        int u, v;
        if (!(cin >> u >> v) or min(u, v) < 1 or max(u, v) > N or u == v)
        {
            die("Invalid input");
        }
        F.emplace_back(u, v);
        ++deg[u];
        ++deg[v];
        ///if(deg[u] > 3 or deg[v] > 3) die("Invalid input");
    }
    vector<int> perm;
    for(int i=1; i<=N; i++)
        perm.pb(i);
    random_shuffle(perm.begin(),perm.end());
    for(int i=0; i<N; i++)
        cdjt[perm[i]]=i+1;
    vector<pair<int,int>> FF;
    for(auto x:F)
        FF.pb({perm[x.first-1],perm[x.second-1]});
    vector<bool> visited(N + 1, false);
    function<void(int)> visit = [&](int x)
    {
        visited[x] = true;
        for (auto [a, b] : F)
        {
            if (b == x) swap(a, b);
            if (a != x or visited[b]) continue;
            visit(b);
        }
    };
    visit(1);
    if (not all_of(visited.begin() + 1, visited.end(), [](bool b)
{
    return b;
}))
    {
        die("Invalid input");
    }

    phase = MARK;
    T = mark(F, dest);
    cout << "mark(";
    print_vector(F);
    cout << ", " << dest << ") returned ";
    print_vector(T);
    cout << endl;
    if (T.size() != static_cast<size_t>(N)) die("Invalid return value of mark");
    for (int x : T)
    {
        if (x < 0 or x > tieLimit) die("Invalid return value of mark");
    }

    phase = LOCATE;
    cout << "Enter curr: ";
    if (!(cin >> curr) or curr < 1 or curr > N) die("Invalid input");
    cout << "locate(";
    print_vector(FF);
    cout << ", " << curr << ", " << T[cdjt[curr] - 1] << ")" << endl;
    locate(FF, curr, T[cdjt[curr] - 1]);
    if (curr == perm[dest-1])
    {
        cout << "Correct: at most " << *max_element(T.begin(), T.end()) << " tie(s) per room" << endl;
    }
    else
    {
        assert(0);
        cout << "Not correct: current position is " << curr << endl;
    }
    return 0;
}
*/

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: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40