Submission #1191233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191233		Unforgettablepl	The Ties That Guide Us (CEOI23_incursion)	C++20	12 / 100	149 ms	7928 KiB

incursion

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

// #define int long long

// SUBTASK 1

vector<int> mark(vector<pair<int,int>> F,int safe){
    int N = F.size()+1;
    vector<int> direction(N);
    vector<vector<int>> adj(N+1);
    for(int i=0;i<N-1;i++){
        adj[F[i].first].emplace_back(F[i].second);
        adj[F[i].second].emplace_back(F[i].first);
    }
    function<void(int,int,int)> dfs = [&](int x,int p,int dep){
        direction[x-1]=dep%3;
        for(int&i:adj[x])if(i!=p)dfs(i,x,dep+1);
    };
    dfs(safe,-1,0);
    return direction;
}

void locate(vector<pair<int,int>> F,int curr,int t){
    int N = F.size()+1;
    vector<int> pos;
    vector<vector<int>> adj(N+1);
    for(int i=0;i<N-1;i++){
        adj[F[i].first].emplace_back(F[i].second);
        adj[F[i].second].emplace_back(F[i].first);
    }
    {
        vector<int> dep(N+1);
        function<int(int,int)> dfs = [&](int x,int p){
            dep[x]=1;
            for(int&i:adj[x])if(i!=p)dep[x]=max(dep[x],dfs(i,x)+1);
            return dep[x];
        };
        dfs(curr,-1);
        for(int i=1;i<=N;i++)
            sort(adj[i].begin(),adj[i].end(),[&](const int &a,const int &b){return dep[a]>dep[b];});
    }
    function<bool(int,int)> dfs = [&](int x,int p){
        int newt = visit(x);
        if((newt+1)%3!=t){
            visit(p);
            return false;
        }
        t = newt;
        for(int&i:adj[x])if(i!=p)if(dfs(i,x))return true;
        return true;
    };
    for(int&i:adj[curr])if(dfs(i,curr))break;
}

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