제출 #1251646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251646		yeyso2	Migrations (IOI25_migrations)	C++20	0 / 100	0 ms	408 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int u, vector<vector<int>> &adj, vector<int> &dist)
{
    for (int v : adj[u])
    {
        dist[v] = dist[u] + 1;
        dfs(v, adj, dist);
    }
}
int send_message(int N, int i, int Pi){
    return Pi + 1;
}

pair<int, int> longest_path(vector<int> S){
    int N = S.size();

    vector<vector<int>> adj(N, vector<int>());
    for (int i = 1; i < (int)S.size(); i++){
        S[i] --;
        //cout << S[i] << " ";
        adj[S[i]].push_back(i);
    }

    vector<int> dist(N, 0);
    dfs(0, adj, dist);
    /*for(int i = 0; i < (int)adj.size(); i ++){
        cout << i << " : ";
        for(int j = 0; j < (int)adj[i].size(); j ++){
            cout << adj[i][j] << " ";
        } cout << "\n";
    }*/
    int max_dist = 0;
    for (int i = 0; i < (int)dist.size(); i++){
        if (dist[i] > dist[max_dist]){
            max_dist = i;
        }
    }
    /*vector<int> dist2(N, 0);
    dfs(max_dist, adj, dist2);
    int max_dist2 = 0;
    for (int i = 0; i < (int)dist2.size(); i++){
        if (dist2[i] > dist[max_dist2]){
            max_dist2 = i;
        }
    }*/
    return {0, max_dist};
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o main grader.cpp migrations.cpp < io.txt

6
0 0 2 2 2
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 70