Submission #1037061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037061		model_code	The Ties That Guide Us (CEOI23_incursion)	C++17	100 / 100	406 ms	15528 KiB

incursion

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

int n;
vector<vector<int>> adj;
vector<int> parent;
vector<int> depth;
vector<int> subtree_size;

void dfs(int from, int d = 0) {
    depth[from] = d;
    for (int j: adj[from]) {
        if (j == parent[from]) continue;
        parent[j] = from;
        dfs(j, d + 1);
        subtree_size[from] += subtree_size[j];
    }
}

int find_center(int treasure_pos) {
    parent.assign(n, -1);
    depth.assign(n, -1);
    subtree_size.assign(n, 0);

    dfs(treasure_pos);
    int end1 = 0;
    for (int i = 1; i < n; ++i)
        if (depth[i] > depth[end1]) end1 = i;

    parent[end1] = -1;
    dfs(end1);
    int end2 = 0;
    for (int i = 1; i < n; ++i)
        if (depth[i] > depth[end2]) end2 = i;

    int center = end2;
    while (depth[center] * 2 > depth[end2] + 1) center = parent[center];

    subtree_size.assign(n, 1);
    parent[center] = -1;
    dfs(center);
    return center;
}

void to_adj_list(const vector<pair<int, int>>& edges) {
    n = edges.size() + 1;
    adj.assign(n, {});
    for (auto [a, b]: edges) {
        --a;
        --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}

vector<int> mark(vector<pair<int, int>> F, int safe) {
    --safe;
    to_adj_list(F);
    find_center(safe);
    vector<int> ties(n, 0);
    do {
        ties[safe] = 1;
        safe = parent[safe];
    } while (safe != -1);
    return ties;
}

void locate(vector<pair<int, int>> F, int curr, int t) {
    --curr;
    to_adj_list(F);
    find_center(0);
    while (t == 0 && parent[curr] != -1) {
        curr = parent[curr];
        assert(curr != -1);
        t = visit(curr + 1);
    }
    for (;;) {
        sort(adj[curr].begin(), adj[curr].end(), [&](int a, int b){ return subtree_size[a] > subtree_size[b]; });
        bool found = false;
        for (int j: adj[curr]) {
            if (j == parent[curr]) continue;
            t = visit(j + 1);
            if (t) {
                found = true;
                curr = j;
                break;
            }
            t = visit(curr + 1);
        }
        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