Submission #1156964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156964		Pacybwoah	Unique Cities (JOI19_ho_t5)	C++20	32 / 100	178 ms	43684 KiB

joi2019_ho_t5

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<cmath>
#include<set>
using namespace std;
vector<vector<int>> graph;
vector<int> maxd, maxu, ans;
// dep, unique
void dfs1(int node, int parent){
    multiset<pair<int, int>> s;
    for(auto &x: graph[node]){
        if(x == parent) continue;
        dfs1(x, node);
        maxd[node] = max(maxd[node], maxd[x] + 1);
        s.emplace(maxd[x] + 1, maxu[x] + 1);
    }
    if(!s.empty()){
        auto iter = prev(s.end());
        if((int)s.size() == 1) maxu[node] = (*iter).second;
        else{
            auto iter2 = prev(iter);
            if((*iter2).first < (*iter).second) maxu[node] = (*iter).second;
        }
    }
}
void dfs2(int node, int parent, int upd, int upu){
    multiset<pair<int, int>> s;
    for(auto &x: graph[node]){
        if(x == parent) continue;
        s.emplace(maxd[x] + 1, maxu[x] + 1);
    }
    if(node != 1) s.emplace(upd + 1, upu + 1);
    if(!s.empty()){
        auto iter = prev(s.end());
        if((int)s.size() == 1) ans[node] = 1;
        else{
            auto iter2 = prev(iter);
            if((*iter2).first < (*iter).second) ans[node] = 1;
        }
    }
    for(auto &x: graph[node]){
        if(x == parent) continue;
        s.erase(s.find(make_pair(maxd[x] + 1, maxu[x] + 1)));
        int downd = 0, downu = 0;
        if(!s.empty()){
            auto iter = prev(s.end());
            downd = max(downd, (*iter).first);
            if((int)s.size() == 1) downu = max(downu, (*iter).second);
            else{
                auto iter2 = prev(iter);
                if((*iter2).first < (*iter).second) downu = max(downu, (*iter).second);
            }
        }
        dfs2(x, node, downd, downu);
        s.insert(make_pair(maxd[x] + 1, maxu[x] + 1));
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    graph.resize(n + 1);
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
    }
    maxd.resize(n + 1);
    maxu.resize(n + 1);
    ans.resize(n + 1);
    dfs1(1, 1);
    dfs2(1, 1, 1, 1);
    for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run pE.cpp

• Subtask 1: 0 / 4
• Subtask 2: 32 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32