Submission #1098099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098099		onlk97	The Ties That Guide Us (CEOI23_incursion)	C++17	0 / 100	89 ms	14916 KiB

incursion

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

vector <int> mark(vector <pair <int,int> > F,int safe){
    int n=F.size()+1;
    vector <int> g[n];
    for (auto&i:F){
        i.first--; i.second--;
        g[i.first].push_back(i.second);
        g[i.second].push_back(i.first);
    }
    safe--;
    vector <int> dist(n,-1);
    queue <int> q;
    q.push(safe);
    dist[safe]=0;
    while (!q.empty()){
        int tp=q.front(); q.pop();
        for (int i:g[tp]){
            if (dist[i]==-1){
                dist[i]=(dist[tp]+1)%3;
                q.push(i);
            }
        }
    }
    return dist;
}

int n,sz[50000];
vector <int> g[50000];
vector <pair <int,int> > vsz[50000];
void dfs0(int cur,int prv){
    sz[cur]=1;
    for (int i:g[cur]){
        if (i==prv) continue;
        dfs0(i,cur);
        sz[cur]+=sz[i];
    }
}
void chroot(int nw,int ol){
    sz[ol]-=sz[nw];
    sz[nw]+=sz[ol];
}
void dfs1(int cur,int prv){
    if (vsz[cur].empty()){
        for (int i:g[cur]) vsz[cur].push_back({sz[i],i});
        sort(vsz[cur].begin(),vsz[cur].end(),greater <pair <int,int> >());
    }
    for (int i:g[cur]){
        if (i==prv) continue;
        chroot(i,cur);
        dfs1(i,cur);
        chroot(cur,i);
    }
}
void locate(vector <pair <int,int> > F,int curr,int t){
    n=F.size()+1;
    for (auto&i:F){
        i.first--; i.second--;
        g[i.first].push_back(i.second);
        g[i.second].push_back(i.first);
    }
    curr--;
    dfs0(0,-1);
    dfs1(0,-1);
    map <int,int> mp;
    mp[curr]=t;
    while (1){
        bool done=0;
        for (pair <int,int> i:vsz[curr]){
            if (mp.find(i.second)!=mp.end()) continue;
            int tp=visit(i.second+1);
            mp[i.second]=tp;
            if (tp!=(mp[curr]+2)%3){
                visit(curr+1);
            } else {
                curr=tp;
                done=1;
                break;
            }
        }
        if (!done) break;
    }
}

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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40