Submission #1224037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224037		spetr	The Ties That Guide Us (CEOI23_incursion)	C++20	30 / 100	204 ms	16060 KiB

incursion

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

using namespace std;
#define vl vector <long long>
#define ll long long
#define vll vector<vector<long long>>

vll graf;
vector<int> ans;
set<ll> vis;
vl counts;

void dfs(ll x, ll d){
    ans[x-1] = d;
    vis.insert(x);
    for (ll i = 0; i < graf[x].size(); i++){
        ll v = graf[x][i];
        auto exist = vis.find(v);
        if (exist == vis.end()){
            dfs(v, d+1);
        }
    }
    return;
}

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
    vis.clear();
    graf.clear();
    ans.clear();
    long long N = F.size()+1;

    ans.resize(N,0);
    for (ll i = 0; i < N+1; i++){graf.push_back({});}
    for (ll i = 0; i < F.size(); i++){
        pair p = F[i];
        graf[p.first].push_back(p.second);
        graf[p.second].push_back(p.first);
    }

    dfs(safe, 0);
    return ans;
}
void step(ll x, ll dist){
    if (dist == 0){
        return;
    }

    vl vektor = graf[x];
    vector<pair<ll,ll>> opt;
    for (ll i = 0; i < vektor.size(); i++){
        opt.push_back({counts[vektor[i]], vektor[i]});
    }
    sort(opt.begin(), opt.end());
    reverse(opt.begin(), opt.end());
    for (ll i = 0; i < opt.size(); i++){
        ll v = opt[i].second;
        auto exist = vis.find(v);
        if (exist == vis.end()){
            ll p = visit(v);
            vis.insert(v);
            if (p < dist){
                step(v, p);
                break;
            }
            else {p = visit(x);}
        }
    }

    return;
}

set<ll> y;
ll find_count(ll x){
    y.insert(x);
    ll suma = 1;
    for (ll i = 0; i < graf[x].size(); i++){
        auto exist = y.find(graf[x][i]);
        if (exist == y.end()){
            suma += find_count(graf[x][i]);
        }
    }

    counts[x] = suma;
    return suma;

}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
    vis.clear();
    graf.clear();

    long long N = F.size()+1;
    counts.resize(N+1);
    for (ll i = 0; i < N+1; i++){graf.push_back({});}
    for (ll i = 0; i < F.size(); i++){
        pair p = F[i];
        graf[p.first].push_back(p.second);
        graf[p.second].push_back(p.first);
    }
    

    find_count(curr);
    vis.insert(curr);
    step(curr, t);


    
    return;
}

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