Submission #1174256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174256		LucaIlie	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	30 ms	6436 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];
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;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        calcParents( v, u );
    }
}

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();
    printf( "%d %d\n", n, centroids.size() );
    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();
    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 );
    calcParents( centroids[0], 0 );
    calcSizes( centroids[0], 0 );

    int v = curr;
    while ( 1 ) {
        vis[v] = true;
        if ( t == 0 ) {
            if ( parent[v] == 0 ) {
                parent[centroids[0]] = centroids[1];
                parent[centroids[1]] = centroids[0];
            }
            v = parent[v];
            t = visit( v );
        } else {
            int maxSz = -1, nxt = -1;
            for ( int u: adj[v] ) {
                if ( u != parent[v] && !vis[u] && sizee[u] >= maxSz ) {
                    nxt = u;
                    maxSz = u;
                }
            }
            if ( nxt == -1 )
                return;
            v = nxt;
            t = visit( v );
        }
    }
}

Compilation message (stderr)

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:69:18: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   69 |     printf( "%d %d\n", n, centroids.size() );
      |                 ~^        ~~~~~~~~~~~~~~~~
      |                  |                      |
      |                  int                    std::vector<int>::size_type {aka long unsigned int}
      |                 %ld

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