Submission #1108396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108396		salmon	Unique Cities (JOI19_ho_t5)	C++14	4 / 100	2057 ms	85192 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;

int N;
int M;
vector<int> adjlst[200100];
int u,v;
int parent[200100];
int lst[200100];
int d1,d2;
bool diam[200100];
int d[200100];
int md[200100];
int pre[200100];
vector<int> path[200100];
int h;
long long int ans[200100];
int c;
int num;

vector<pair<int,int>> uni;
map<int,int> tooken;
//3Na 3Si 3Al 12O

void dfs(int i, int p, int de){
    d[i] = de;
    md[i] = de;
    parent[i] = p;

    for(int j : adjlst[i]){
        if(j == p) continue;
        dfs(j, i, de + 1);
        md[i] = max(md[i],md[j]);
    }
}

void solve(int i, int pa);

void recurse(int i, int j, int pa){
    uni.push_back({d[i],i});

    auto it = lower_bound(uni.begin(),uni.end(),make_pair(pa,-1) );

    vector<int> undo;
    int pa1 = d[i] + 1 - (md[j] - d[i] - 1);
    while(it != uni.end() && it -> first < pa1){
        undo.push_back(lst[it -> second]);
        tooken[lst[it -> second]]++;
        advance(it,1);
    }

    solve(j,max(pa1,pa));
    uni.pop_back();

    reverse(undo.begin(),undo.end());
    for(int i : undo){
        tooken[i]--;
        if(tooken[i] == 0) tooken.erase(i);
    }
}

void solve(int i, int pa){//printf("i: %d\n",i);
    if(d[i] <= d[c]){
        int child = -1;

        for(int j : path[i]){
            if(j != parent[i]) child = j;
        }

        int num1 = d[i];

        for(int j : adjlst[i]){
            if(j == child || j == parent[i]) continue;
            num1 = max(num1,md[j]);
        }

        while(!uni.empty() && uni.back().first >= d[i] - (num1 - d[i]) ){
            uni.pop_back();
        }

        uni.push_back({d[i],i});

        if(d[i] == d[c]){
            int h = d[i] + 1 - (num - d[i] - 1);
            int it = 0;
            while(it != uni.size() && uni[it].first < h){
                tooken[lst[uni[it].second]]++;
                it++;
            }
            solve(child,h);
        }
        else solve(child,2);
    }
    else{
/*if(i == 0){
    for(pair<int,int> ii : tooken){
        printf("t %d %d\n",ii.first,ii.second);
    }
}*/
        map<int,int,greater<int>> mep;

        for(int j : adjlst[i]){
            if(j == parent[i]) continue;
            mep[md[j]]++;
        }

        ans[i] = tooken.size();
        if(mep.empty()) return;


        if(mep.begin() -> second == 1){
            int special;
            for(int j : adjlst[i]){
                if(j == parent[i]) continue;
                if(md[i] == md[j]) special = j;
            }

            auto it1 = mep.begin();
            advance(it1,1);

            int num;

            vector<int> undo1;
            if(it1 != mep.end()){
                num = d[i] - (it1 -> first - d[i]);
                while(!uni.empty() && uni.back().first >= num){
                    if(uni.back().first < pa){
                        tooken[uni.back().second]--;
                        if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second);
                    }
                    undo1.push_back(uni.back().second);
                    uni.pop_back();
                }
            }

            uni.push_back({d[i],i});

            auto it = lower_bound(uni.begin(),uni.end(),make_pair(pa,-1));

            vector<int> undo;
            int pa1 = d[i] + 1 - (md[special] - d[i] - 1);
            //printf("%d\n",uni.back().first);
            while(it != uni.end() && it -> first < pa1){
                undo.push_back(lst[it -> second]);
                tooken[lst[it -> second]]++;
                advance(it,1);
            }

            solve(special,max(pa,pa1));
            uni.pop_back();

            reverse(undo.begin(),undo.end());
            for(int i : undo){
                tooken[i]--;
                if(tooken[i] == 0) tooken.erase(i);
            }

            for(int j : adjlst[i]){
                if(j == parent[i]) continue;
                if(md[j] == md[i]) continue;
                int num;

                num = d[i] - (md[i] - d[i]);
                while(!uni.empty() && uni.back().first >= num){
                    if(uni.back().first < pa){
                        tooken[uni.back().second]--;
                        if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second);
                    }
                    undo1.push_back(uni.back().second);
                    uni.pop_back();
                }

                recurse(i,j,pa);

                reverse(undo1.begin(),undo1.end());
                for(int i : undo1){
                    uni.push_back({d[i],i});
                    if(uni.back().first < pa){
                        tooken[uni.back().second]++;
                    }
                }
                undo1.clear();
            }
        }
        else{
            vector<int> undo1;
            int num = d[i] - (md[i] - d[i]);
            while(!uni.empty() && uni.back().first >= num){
                if(uni.back().first < pa){
                    tooken[uni.back().second]--;
                    if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second);
                }
                undo1.push_back(uni.back().second);
                uni.pop_back();
            }

            for(int j : adjlst[i]){
                if(j == parent[i]) continue;
                recurse(i,j,pa);
            }

            reverse(undo1.begin(),undo1.end());
            for(int i : undo1){
                uni.push_back({d[i],i});
                if(uni.back().first < pa){
                    tooken[uni.back().second]++;
                }
            }
        }
    }
}

int main(){

    scanf(" %d",&N);
    scanf(" %d",&M);

    for(int i = 0; i < N - 1; i++){
        scanf(" %d",&u);
        scanf(" %d",&v);
        u--;
        v--;

        adjlst[u].push_back(v);
        adjlst[v].push_back(u);
    }

    for(int i = 0; i < N; i++){
        scanf(" %d",&lst[i]);
        lst[i]--;
    }

    dfs(1,-1,0);

    pair<int,int> ii = {0,-1};

    for(int i = 0; i < N; i++){
        ii = max(ii, {d[i],i});
        ans[i] = 0;
    }

    d1 = ii.second;

    dfs(d1,-1,0);

    ii = {0,-1};

    for(int i = 0; i < N; i++){
        ii = max(ii, {d[i],i});
    }

    d2 = ii.second;

    num = ii.first;

    h = d2;
    for(int i = 0; i < num; i++){
        path[h].push_back(parent[h]);
        path[parent[h]].push_back(h);
        h = parent[h];
    }

    if(num % 2 == 1){
//printf("%d %d\n",d1,d2);
        c = d2;
        for(int i = 0; i < num / 2 + 1; i++){
            c = parent[c];
        }

        solve(d1,0);
//printf("S");
        dfs(d2,-1,0);

        c = d1;
        for(int i = 0; i < num / 2 + 1; i++){
            c = parent[c];
        }

        uni.clear();
        tooken.clear();
        solve(d2,0);
//printf("S\n\n");
    }
    else{
        //printf("%d %d\n",d1,d2);
        c = d2;

        for(int i = 0; i < num / 2 + 1; i++){
            c = parent[c];
        }

        solve(d1,0);
//printf("S");
        dfs(d2,-1,0);

        c = d1;
        for(int i = 0; i < num/2 + 1; i++){
            c = parent[c];
        }

        uni.clear();
        tooken.clear();
        solve(d2,0);
//printf("S\n\n");
    }

    for(int i = 0; i < N; i++){
        printf("%d\n",ans[i]);
    }
}
/*
6 4
6 1
1 2
2 3
3 4
3 5
1 2 1 2 4 4

4 4
1 2
1 3
1 4
1 2 3 4

7 7
1 2
1 3
1 4
2 5
3 6
4 7
1 2 3 4 5 6 7

5 1
2 1
3 1
4 1
5 3
1 1 1 1 1
*/

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void solve(int, int)':
joi2019_ho_t5.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             while(it != uni.size() && uni[it].first < h){
      |                   ~~~^~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:308:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  308 |         printf("%d\n",ans[i]);
      |                 ~^    ~~~~~~
      |                  |         |
      |                  int       long long int
      |                 %lld
joi2019_ho_t5.cpp:215:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:216:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:219:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:220:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:229:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void solve(int, int)':
joi2019_ho_t5.cpp:149:18: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
  149 |             solve(special,max(pa,pa1));
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~

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