Submission #1174292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174292		LucaIlie	The Ties That Guide Us (CEOI23_incursion)	C++20	30 / 100	133 ms	7664 KiB

incursion

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

using namespace std;

const int MAX_N = 4.5e4;
bool vis[MAX_N + 1];
int sizee[MAX_N + 1], parent[MAX_N + 1], maxDepth[MAX_N + 1];
vector<int> adj[MAX_N + 1];

void calcSizes( int u, int p ) {
    sizee[u] = 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        calcSizes( v, u );
        sizee[u] += sizee[v];
    }
}

int n;
vector<int> centroids;
void findCentroids( int u, int p ) {
    int maxSize = n - sizee[u];
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        findCentroids( v, u );
        maxSize = max( maxSize, sizee[v] );
    }
    if ( maxSize <= n / 2 )
        centroids.push_back( u );
}

vector<int> ties;
void assignTies( int u, int p, int safe ) {
    if ( u == safe )
        ties[u - 1] = 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        assignTies( v, u, safe );
        ties[u - 1] += ties[v - 1];
    }
}

void calcParents( int u, int p ) {
    parent[u] = p;
    maxDepth[u] = 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        calcParents( v, u );
        maxDepth[u] = max( maxDepth[u], maxDepth[v] + 1 );
    }
}

vector<int> mark( vector<pair<int, int>> F, int safe ) {
    n = F.size() + 1;
    centroids.clear();
    for ( int v = 1; v <= n; v++ )
        adj[v].clear(), sizee[v] = 0;
    for ( int i = 0; i < F.size(); i++ ) {
        adj[F[i].first].push_back( F[i].second );
        adj[F[i].second].push_back( F[i].first );
    }

    calcSizes( 1, 0 );
    findCentroids( 1, 0 );
    ties.clear();
    ties.resize( n );
    assignTies( centroids[0], 0, safe );
    return ties;
}

void locate( vector<std::pair<int, int>> F, int curr, int t ) {
    n = F.size() + 1;
    centroids.clear();
    for ( int v = 1; v <= n; v++ )
        adj[v].clear(), sizee[v] = 0;
    for ( int i = 0; i < F.size(); i++ ) {
        adj[F[i].first].push_back( F[i].second );
        adj[F[i].second].push_back( F[i].first );
    }

    calcSizes( 1, 0 );
    findCentroids( 1, 0 );
    if ( centroids.size() == 2 )
        swap( centroids[0], centroids[1] );
    calcParents( centroids[0], 0 );
    calcSizes( centroids[0], 0 );
    int v = curr, t0 = 0;
    bool change = false;
    while ( 1 ) {
        vis[v] = true;
        if ( v == centroids[0] && centroids.size() == 2 )
            t0 = t;
        if ( t == 0 && (!change || v != centroids[0]) ) {
            if ( parent[v] == 0 ) {
                parent[centroids[0]] = centroids[1];
                parent[centroids[1]] = centroids[0];
                change = true;
            }
            v = parent[v];
            t = visit( v );
        } else {
            int maxSz = -1, nxt = -1;
            for ( int u: adj[v] ) {
                if ( (u != parent[v] || (u == centroids[0] && centroids.size() == 2)) && (!vis[u] || (u == centroids[0] && t0 == 1)) ) {
                    if ( sizee[u] > maxSz || (sizee[u] == maxSz && rand() % 2 == 0) ) {
                        nxt = u;
                        maxSz = sizee[u];
                    }
                }
            }
            if ( nxt == -1 )
                return;
            v = nxt;
            t = visit( v );
        }
    }
}

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