Submission #1064748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064748		beaconmc	The Ties That Guide Us (CEOI23_incursion)	C++17	12 / 100	326 ms	40044 KiB

incursion

#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;



ll sub[50000];
vector<ll> edges[50000];
ll ancc[50000][30];
ll par[50000];
ll visited[50000];
ll depth[50000];
ll unsure[50000];

ll anc(ll a, ll x){
    if (a==1) return 1;
    if (x==0) return par[a];
    if (ancc[a][x] != -1) return ancc[a][x];
    return ancc[a][x] = anc(anc(a,x-1),x-1);
}

ll lca(ll a, ll b){
    if (depth[a] < depth[b]) swap(a,b);
    FORNEG(i,29,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);
    if (a==b) return a;
    FORNEG(i,29,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
    return par[a];
}

void dfs(ll a, ll p, ll d){
    depth[a] = d;
    par[a] = p;
    sub[a] = 1;
    for (auto&i : edges[a]){
        if (i != p) dfs(i,a,d+1), sub[a] += sub[i];
    }
}


vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
    vector<int> ties(F.size()+1);
    FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
    FOR(i,0,50000) FOR(j,0,30) ancc[i][j] = -1;
    for (auto&i : F){
        edges[i.first].push_back(i.second);
        edges[i.second].push_back(i.first);
    }
    dfs(1, -1, 0);
    ll n = F.size()+1;
    FOR(i,1,n+1){
        if (safe == i){
            ties[i-1] = 2;
            continue;
        }
        vector<ll> idk;
        for (auto&k : edges[i]){
            if (k==par[i])idk.push_back(n-sub[i]);
            else idk.push_back(sub[k]);
        }

        sort(idk.begin(), idk.end());

        ll nxt = -1;
        ll sz = 0;
        for (auto&k : edges[i]){
            if (k != par[i] && lca(k, safe) == k) nxt = k;
        }
        if (nxt==-1) nxt = par[i];
        if (nxt == par[i]) sz = n-sub[i];
        else sz = sub[nxt];

        if (sz == idk[idk.size()-1]){
            ties[i-1] = 1;
        }else{
            ties[i-1] = 0;
        }
    }
    return ties;


}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {

    FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0, visited[i] = 0, unsure[i] = 0;
    FOR(i,0,50000) FOR(j,0,30) ancc[i][j] = -1;
    for (auto&i : F){
        edges[i.first].push_back(i.second);
        edges[i.second].push_back(i.first);
    }
    dfs(1, -1, 0);
    ll n = F.size()+1;
    ll here = t;
    while(here != 2){
        visited[curr] += 1;
        vector<vector<ll>> idk;
        for (auto&k : edges[curr]){
            if (par[curr] == k)idk.push_back({n-sub[curr], par[curr]});
            else idk.push_back({sub[k], k});
        }

        sort(idk.begin(), idk.end());


        if (idk.size()==2 && idk[0][0]==idk[1][0]) unsure[curr] = 1;
        if (idk.size()==3){
            if (here==1 && idk[2][0]==idk[1][0]) unsure[curr] =1;
            if (here==0 && idk[2][0]!=idk[1][0]) unsure[curr] = 1;
        }





        if (here==0){
            if (visited[idk[0][1]] && !unsure[idk[0][1]] && unsure[curr]) curr = idk[1][1], here = visit(curr);
            else curr = idk[0][1], here = visit(curr);
        }else{
             if (visited[idk[idk.size()-1][1]] && !unsure[idk[idk.size()-1][1]] && unsure[curr]) curr = idk[idk.size()-2][1], here = visit(curr);
             else curr = idk[idk.size()-1][1], here = visit(curr);
        }
    }
    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: 12 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40