제출 #1198271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198271		Zbyszek99	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	147 ms	6944 KiB

incursion

#include "incursion.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int n;
vi graph[45001];
int sub[45001];
int P[45001];
vi marks;

void dfs(int v, int pop)
{
    sub[v] = 1;
    P[v] = pop;
    forall(it,graph[v])
    {
        if(it != pop)
        {
            dfs(it,v);
            sub[v] += sub[it];
        }
    }
}

void dfs_mark(int v, int pop)
{
    if(v == pop) marks[v-1] = 0;
    else
    {
        int best_ = 0;
        forall(it,graph[v])
        {
            if(it != P[v])
            {
                best_ = max(best_,sub[it]);
            }
            else
            {
                best_ = max(best_,n-sub[v]);
            }
        }
        if(best_ == n-sub[v]) marks[v-1] = 1;
        else marks[v-1] = 0;
    }
    forall(it,graph[v])
    {
        if(it != pop)
        {
            dfs_mark(it,v);
        }
    }
}

vi mark(vector<pii> F, int safe) 
{
    n = siz(F)+1;
    rep2(i,1,n) graph[i] = {};
    forall(it,F)
    {
        graph[it.ff].pb(it.ss);
        graph[it.ss].pb(it.ff);
    }
    dfs(safe,safe);
    marks.resize(n,0);
    dfs_mark(safe,safe);
    return marks;
}

void locate(vector<pii> F, int curr, int t) 
{
    n = siz(F)+1;
    rep2(i,1,n) graph[i] = {};
    forall(it,F)
    {
        graph[it.ff].pb(it.ss);
        graph[it.ss].pb(it.ff);
    }
    dfs(1,1);
    int prev = curr;
    while(true)
    {
        if(t == 1)
        {
            int best_ = 0;
            vi bests;
            forall(it,graph[curr])
            {
                if(it == prev) continue;
                if(it != P[curr])
                {
                    if(best_ == sub[it])
                    {
                        bests.pb(it);
                    }
                    else if(best_ < sub[it])
                    {
                        best_ = sub[it];
                        bests = {it};
                    }
                }
                else
                {
                    if(best_ == n-sub[curr])
                    {
                        bests.pb(it);
                    }
                    else if(best_ < n-sub[curr])
                    {
                        best_ = n-sub[curr];
                        bests = {it};
                    }
                }
            }
            rep(i,siz(bests))
            {
                t = visit(bests[i]);
                if(i == siz(bests)-1)
                {
                    prev = curr;
                    curr = bests[i];
                    break;
                }
                else
                {
                    if(t == 1)
                    {
                        t = visit(curr);
                    }
                    else
                    {
                        prev = curr;
                        curr = bests[i];
                        break;
                    }
                }
            }
        }
        else
        {
            vector<pii> rest;
            int best_ = 0;
            forall(it,graph[curr])
            {
                int d = sub[it];
                if(P[curr] == it) d = n - sub[curr];
                best_ = max(best_,d);
            }
            forall(it,graph[curr])
            {
                if(it == prev) continue;
                int d = sub[it];
                if(P[curr] == it) d = n - sub[curr];
                if(d != best_) rest.pb({d,it});
            }
            sort(all(rest));
            reverse(all(rest));
            bool is = 0;
            rep(i,siz(rest))
            {
                t = visit(rest[i].ss);
                if(t == 0)
                {
                    prev = curr;
                    curr = rest[i].ss;
                    is = 1;
                    break;
                }
                else
                {
                    t = visit(curr);
                }
            }
            if(!is) break;
        }
    }
}

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