Submission #1191220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191220		Unforgettablepl	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	119 ms	8272 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<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);
    }
    function<void(int,int)> dfs = [&](int x,int p){
        pos.emplace_back(x);
        for(int&i:adj[x])if(i!=p)dfs(i,x);
    };
    for(int i=1;i<=N;i++)if(adj[i].size()==1){dfs(i,-1);break;}
    int goMe = -1;
    for(int i=0;i<N;i++)if(pos[i]==safe)goMe=i;
    if(N&1 and goMe==N/2){
        // EDGE CASE
        for(int i=0;i<goMe;i++)direction[pos[i]-1]=1;
        for(int i=goMe+1;i<N;i++)direction[pos[i]-1]=1;
    } else {
        if(N&1){
            if(goMe<N/2){
                for(int i=N/2;i<N;i++)direction[pos[i]-1]=1;
                for(int i=goMe;i<N/2;i++)direction[pos[i]-1]=0;
                for(int i=0;i<goMe;i++)direction[pos[i]-1]=1;
            } else {
                for(int i=0;i<=N/2;i++)direction[pos[i]-1]=1;
                for(int i=N/2+1;i<=goMe;i++)direction[pos[i]-1]=0;
                for(int i=goMe+1;i<N;i++)direction[pos[i]-1]=1;
            }
        } else {
            if(goMe<N/2){
                for(int i=N/2;i<N;i++)direction[pos[i]-1]=1;
                for(int i=goMe;i<N/2;i++)direction[pos[i]-1]=0;
                for(int i=0;i<goMe;i++)direction[pos[i]-1]=1;
            } else {
                for(int i=0;i<N/2;i++)direction[pos[i]-1]=1;
                for(int i=N/2;i<=goMe;i++)direction[pos[i]-1]=0;
                for(int i=goMe+1;i<N;i++)direction[pos[i]-1]=1;
            }
        }
    }
    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);
    }
    function<void(int,int)> dfs = [&](int x,int p){
        pos.emplace_back(x);
        for(int&i:adj[x])if(i!=p)dfs(i,x);
    };
    for(int i=1;i<=N;i++)if(adj[i].size()==1){dfs(i,-1);break;}
    int currPos = -1;
    for(int i=0;i<N;i++)if(pos[i]==curr)currPos=i;
    vector<bool> visited(N);    
    if(N&1){
        while(true){
            visited[currPos]=true;
            if(currPos==N/2){
                if(t==0)return;
                else {
                    if(!visited[currPos+1]){
                        t = visit(pos[++currPos]);
                        continue;
                    }
                    if(!visited[currPos-1]){
                        t = visit(pos[--currPos]);
                        continue;
                    }
                }
            } else if(currPos<N/2){
                if(t==1){
                    t = visit(pos[++currPos]);
                    if(currPos!=N/2 and visited[currPos])return;
                } else if(t==0){
                    if(currPos==0)return;
                    t=visit(pos[--currPos]);
                    if(visited[currPos]){
                        t = visit(pos[++currPos]);
                        return;
                    }
                }
            } else if(currPos>N/2){
                if(t==1){
                    t = visit(pos[--currPos]);
                    if(currPos!=N/2 and visited[currPos]){
                        t = visit(pos[++currPos]);
                        return;
                    }
                } else if(t==0){
                    if(currPos==N-1)return;
                    t=visit(pos[++currPos]);
                    if(visited[currPos])return;
                }
            }
        }
    } else {
        while(true){
            visited[currPos]=true;
            if(currPos<N/2){
                if(t==1){
                    t = visit(pos[++currPos]);
                    if(visited[currPos])return;
                } else if(t==0){
                    if(currPos==0)return;
                    t=visit(pos[--currPos]);
                    if(visited[currPos]){
                        t = visit(pos[++currPos]);
                        return;
                    }
                }
            } else if(currPos>=N/2){
                if(t==1){
                    t = visit(pos[--currPos]);
                    if(visited[currPos]){
                        t = visit(pos[++currPos]);
                        return;
                    }
                } else if(t==0){
                    if(currPos==N-1)return;
                    t=visit(pos[++currPos]);
                    if(visited[currPos])return;
                }
            }
        }
    }
}

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