Submission #1295758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295758		trantrungkein	Unique Cities (JOI19_ho_t5)	C++20	0 / 100	77 ms	14116 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 7;
int vis[N],par[N],num[N],r[N],up[N],down[N],n,l[N];
vector<int> g[N];
int node1, node2, maxx, diameter = 0;
void dfs(int u, int p, int len, int& node){
    if(len > maxx){
        maxx = len;
        node = u;
    }
    for(int v : g[u]) if(v != p) {
        dfs(v,u,len+1,node);
    }
}
void line(int u, int p){
    for(int v : g[u]) if(v != p){
        line(v,u);
        par[v] = u;
    }
}
vector<int> Line;
void push_down(int u, int p,int root){
    for(int v : g[u]) if(v != p && !vis[v]){
        num[v] = root;
        down[v] = down[u] + 1;
        push_down(v,u,root);
        up[u] = max(up[v]+1,up[u]);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int m;
    cin >> n >> m;
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) {int x;cin >> x;}
    maxx = 0;
    dfs(1,0,0,node1);
    maxx = 0;
    dfs(node1,0,0,node2);
    diameter = maxx;
    line(node1,0);
    int tmp2 = node2;
    Line.push_back(tmp2);
    while(tmp2 != node1){
        tmp2 = par[tmp2];
        Line.push_back(tmp2);
    }
    for(int id : Line) vis[id] = true;
    for(int i = 0; i < Line.size(); i++){
        l[Line[i]] = i;
        r[Line[i]] = Line.size() - 1 - i;
        push_down(Line[i],0,Line[i]);
    }
    for(int i = 1; i <= n; i++){
        if(num[i] == 0){
            if(l[i] != r[i]) cout << 1;
            else cout << 0;
        }
        else {
            if(l[num[i]] != r[num[i]]) cout << 1;
            else{
                if(down[i] > up[i]) cout << 1;
                else cout << 0;
            }
        }
        cout <<'\n';
    }
}

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