Submission #1233545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233545		Tenis0206	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	159 ms	8804 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"

using namespace std;

const int nmax = 1e5;

int n;
vector<int> G[nmax + 5];

int w[nmax + 5];

vector<int> t;

int d[nmax + 5];

bool sel[nmax + 5];

void get_w_mark(int nod, int dad = 0)
{
    w[nod] = 1;
    for(auto it : G[nod])
    {
        if(it == dad)
        {
            continue;
        }
        get_w_mark(it, nod);
        w[nod] += w[it];
    }
}

void get_mark(int nod, int dad = 0)
{
    int Max = 0;
    for(auto it : G[nod])
    {
        if(it == dad)
        {
            continue;
        }
        get_mark(it, nod);
        if(w[it] > w[Max])
        {
            Max = it;
        }
    }
    if(n - w[nod] >= w[Max])
    {
        t[nod - 1] = 1;
    }
    if(dad == 0)
    {
        t[nod - 1] = 0;
    }
}

vector<int> mark(vector<pair<int,int>> e, int root)
{
    n = e.size() + 1;
    t.resize(n);
    for(auto it : e)
    {
        G[it.first].push_back(it.second);
        G[it.second].push_back(it.first);
    }
    get_w_mark(root);
    get_mark(root);
    return t;
}

void get_w_locate(int nod, int dad = 0)
{
    d[nod] = dad;
    w[nod] = 1;
    for(auto it : G[nod])
    {
        if(it == dad)
        {
            continue;
        }
        get_w_locate(it, nod);
        w[nod] += w[it];
    }
}

void locate(vector<pair<int,int>> e, int start, int val)
{
    n = e.size() + 1;
    for(int i=1;i<=n;i++)
    {
        G[i].clear();
    }
    for(auto it : e)
    {
        G[it.first].push_back(it.second);
        G[it.second].push_back(it.first);
    }
    get_w_locate(start);
    int nod = start;
    while(true)
    {
        if(sel[nod] && val == 0)
        {
            break;
        }
        sel[nod] = true;
        vector<pair<int,int>> l;
        for(auto it : G[nod])
        {
            if(it == d[nod])
            {
                l.push_back({n - w[nod], it});
            }
            else
            {
                l.push_back({w[it], it});
            }
        }
        sort(l.begin(), l.end(), greater<pair<int,int>>());
        if(val == 1)
        {
            if(l.size() == 1)
            {
                val = visit(l[0].second);
                nod = l[0].second;
            }
            else
            {
                if(l[0].first > l[1].first)
                {
                    val = visit(l[0].second);
                    nod = l[0].second;
                }
                else if(l[1].first > l[2].first)
                {
                    val = visit(l[0].second);
                    if(val == 1)
                    {
                        val = visit(nod);
                        val = visit(l[1].second);
                        nod = l[1].second;
                    }
                    else
                    {
                        nod = l[0].second;
                    }
                }
                else
                {
                    val = visit(l[0].second);
                    if(val == 1)
                    {
                        val = visit(nod);
                        val = visit(l[1].second);
                        if(val == 1)
                        {
                            val = visit(nod);
                            val = visit(l[2].second);
                            nod = l[2].second;
                        }
                        else
                        {
                            nod = l[1].second;
                        }
                    }
                    else
                    {
                        nod = l[0].second;
                    }
                }
            }
        }
        else
        {
            if(l.size() == 1)
            {
                return;
            }
            if(l.size() == 2)
            {
                val = visit(l[1].second);
                nod = l[1].second;
            }
            else
            {
                val = visit(l[1].second);
                if(val == 1)
                {
                    val = visit(nod);
                    val = visit(l[2].second);
                    nod = l[2].second;
                }
                else
                {
                    nod = l[1].second;
                }
            }
        }
    }
}

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