結果

問題 No.2998 Rainbow Christmas Tree
ユーザー 👑 Nachia
提出日時 2024-12-23 03:06:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 110 ms / 3,000 ms
コード長 1,901 bytes
コンパイル時間 971 ms
コンパイル使用メモリ 82,780 KB
最終ジャッジ日時 2025-02-26 16:10:17
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;

void testcase(){
    int N, K; cin >> N >> K;
    vector<vector<int>> P(N-1);
    rep(i,N-1){
        P[i].resize(N);
        rep(a,N){ cin >> P[i][a]; P[i][a]--; }
    }
    vector<pair<int,int>> H(N, {-1,-1}); H[N-1] = {-2,-1};
    vector<pair<int,int>> I(N, {-1,-1}); I[0] = {-2,-1};
    for(int i=0; i<K; i++){
        for(int a=0; a<N; a++) if(a != 0 && H[a].first != -1 && H[a].first != i){
            if(H[P[i][a]].first == -1) H[P[i][a]] = {i,a};
        }
    }
    for(int i=K; i<N-1; i++){
        for(int a=0; a<N; a++) if(a != N-1 && I[a].first != -1 && I[a].first != i){
            if(I[P[i][a]].first == -1) I[P[i][a]] = {i,a};
        }
    }
    int root = -1;
    rep(i,N) if(H[i].first != -1 && I[i].first != -1) root = i;
    vector<int> used(N);
    vector<int> res(N, -2); res[root] = -1;
    for(int p=root; H[p].first>=0; p=H[p].second){
        res[H[p].second] = H[p].first;
        used[H[p].first] = 1;
    }
    for(int p=root; I[p].first>=0; p=I[p].second){
        res[I[p].second] = I[p].first;
        used[I[p].first] = 1;
    }
    rep(i,N-1) if(!used[i]){
        rep(a,N) if(P[i][a] != -1 && res[a] == -2 && res[P[i][a]] != -2){
            res[a] = i;
            used[i] = 1;
            break;
        }
    }
    cout << "Yes\n";
    rep(i,N){
        if(i) cout << " ";
        cout << (res[i]+1);
    } cout << "\n";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}
0