제출 #1233414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233414		yixuan19	Team Coding (EGOI24_teamcoding)	C++20	23 / 100	39 ms	16844 KiB

Main

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

const int taille = 2001;
vector<int> depth(taille,0);
vector<vector<int> > child(taille);
vector <int> languages;
vector <vector<int> > levels(taille, vector<int> (taille,0));
vector<int> used(taille,0);

void dfs(int node){
    for (int c: child[node]){
        depth[c] = depth[node]+1;
        dfs(c);
    }
}
int score = 0;
int swaps = 0;

void dfs2(int node, int lang){
    //cout<<"calling "<<node<<' '<<lang<<' '<<score<<endl;
    if (languages[node] == lang && levels[depth[node]][lang] - used[depth[node]] > 0){
        score++;
        used[depth[node]]++;
    }else if (languages[node] == lang && levels[depth[node]][lang] - used[depth[node]] == 0){
        swaps--;
    }else{
        if (levels[depth[node]][lang] - used[depth[node]] > 0){
            score++;
            used[depth[node]]++;
            swaps++;
        }
    }
    for (int c: child[node]){
        dfs2(c, lang);
    }
}
int main(){
    int N, K, lang, boss;
    cin >> N >> K;
    for (int i = 0; i < N; ++i){
        cin >> lang;
        languages.push_back(lang);
    }
    for (int i = 1; i <= N-1; ++i){
        cin >> boss;
        child[boss].push_back(i);
    }
    dfs(0);

    // for (int i = 0; i < N; ++i){
    //     cout<<depth[i]<<' ';
    // }
    // cout<<endl;
    
    for (int i = 0; i < N; ++i){
        levels[depth[i]][languages[i]]++;
    }
    // for (int i = 0; i < 5; ++i){
    //     //cout<<"depth "<<i<<": ";
    //     for (int j = 0; j < 5; ++j){
    //         cout<<levels[i][j]<<' ';
    //     }
    //     cout<<endl;
    // }
    vector<pair<int,int> > results;
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < N; ++j){
            used[j] = 0;
        }
        score = 0;
        swaps = 0;
        dfs2(i, languages[i]);
        results.push_back(make_pair(score,-swaps));
    }
    // for (auto p: results){
    //     cout<<p.first<<' '<<p.second<<endl;
    // }
    sort(results.rbegin(), results.rend());
    cout<<results[0].first<<' '<<-results[0].second<<endl;
    
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 19
• Subtask 3: 0 / 27
• Subtask 4: 23 / 23
• Subtask 5: 0 / 19