Submission #1081397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081397		Evirir	The Ties That Guide Us (CEOI23_incursion)	C++17	100 / 100	281 ms	13472 KiB

incursion

#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;

#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

int n;
vector<vector<int>> adj;
vector<int> sub, prt;
ii root = {-1, -1};

void init()
{
    adj.resize(n); prt.resize(n); sub.resize(n);
    forn(i,0,n) adj[i].clear();
}

int Visit(int u){ return visit(u + 1); }

void getSub(int u, int p)
{
    sub[u] = 1;
    for (const auto v : adj[u])
    {
        if (v == p) continue;
        getSub(v, u);
        sub[u] += sub[v];
    }
}

bool iscentroid(int u)
{
    if (2 * (n - sub[u]) > n) return false;
    for (const auto& v : adj[u])
    {
        if (v == prt[u]) continue;
        if (2 * sub[v] > n) return false;
    }
    return true;
}

bool isRoot(int u)
{
    // assert(u != -1);
    return root.F == u || root.S == u;
}

void getPrt(int u, int p)
{
    prt[u] = p;
    for (const auto v : adj[u])
    {
        if (v == p) continue;
        getPrt(v, u);
    }
}

void getRoot()
{
    getSub(0, -1);
    getPrt(0, -1);
    int u = 0;
    while (!iscentroid(u))
    {
        for (const auto v : adj[u])
        {
            if (v == prt[u]) continue;
            if (2 * sub[v] > n)
            {
                u = v;
                break;
            }
        }
    }
    root.F = u;
    for (const auto v : adj[u])
    {
        if (iscentroid(v)) root.S = v;
    }
}

vector<int> mark(vector<pair<int, int>> edges, int safe)
{
    n = sz(edges) + 1;
    init();
    safe--;
    for (auto& [u, v] : edges) { u--; v--; }
    for (auto [u, v] : edges)
    {
        adj[u].pb(v);
        adj[v].pb(u);
    }
    getRoot();
    getPrt(root.F, -1);

    int u = safe;
    vector<int> res(n, 0);
    while (!isRoot(u))
    {
        res[u] = 1;
        u = prt[u];
    }
    res[u] = 1;
    return res;
}

void locate(vector<pair<int, int>> edges, int src, int tcnt)
{
    n = sz(edges) + 1;
    init();
    src--;
    for (auto& [u, v] : edges) { u--; v--; }
    for (auto [u, v] : edges)
    {
        adj[u].pb(v);
        adj[v].pb(u);
    }
    getRoot();
    getPrt(root.F, -1);
    getSub(root.F, -1);

    bool vst[n]{};
    int u = src;
    vst[u] = 1;
    while (!isRoot(u) && tcnt == 0)
    {
        u = prt[u];
        tcnt = Visit(u);
        vst[u] = 1;
    }
    if (tcnt == 0)  // go to other root
    {
        u = (u == root.F ? root.S : root.F);
        tcnt = Visit(u);
        vst[u] = 1;
        // assert(tcnt > 0);
    }

    while (true)
    {
        vector<int> nxt;
        for (const auto v : adj[u])
        {
            if (vst[v] || v == prt[u]) continue;
            nxt.pb(v);
        }
        sort(all(nxt), [](int v1, int v2){ return sub[v1] > sub[v2]; });
        // assert(sz(nxt) <= 2);
        bool found = 0;
        for (const auto v : nxt)
        {
            tcnt = Visit(v);
            if (tcnt == 1)
            {
                found = 1;
                u = v;
                break;
            }
            tcnt = Visit(u);
        }
        if (!found) return;
    }
}

Compilation message (stderr)

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

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