Submission #1108305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108305		salmon	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	70 ms	23624 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;

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){//printf("i: %d\n",i);
    if(d[i] <= d[c]){
        int child;

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

        int num = d[i];

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

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

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

        if(d[i] == d[c]){
            int h = min(d[i] + 1 - (num - d[i] - 1),d[c] - 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{

        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;

            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);
                    }
                    uni.pop_back();
                }
            }

            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);
            while(it != uni.end() && it -> first < pa1){
                undo.push_back(lst[it -> second]);
                tooken[lst[it -> second]]++;
                advance(it,1);
            }

            uni.push_back({d[i],i});
            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;
                vector<int> undo1;

                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);
                    }
                    uni.pop_back();
                }
                auto it = upper_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);
                }

                uni.push_back({d[i],i});
                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);
                }
                reverse(undo1.begin(),undo1.end());
                for(int i : undo1){
                    uni.push_back({d[i],i});
                }
            }
        }
        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);
                }
                uni.pop_back();
            }

            for(int j : adjlst[i]){
                if(j == parent[i]) continue;
                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);
                }

                uni.push_back({d[i],i});
                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);
                }
            }

            reverse(undo1.begin(),undo1.end());
            for(int i : undo1){
                uni.push_back({d[i],i});
            }
        }
    }
}

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]);
    }

    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;

    int 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){
        //for(int i = 0;)
    }
    else{
        c = d2;

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

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

        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
*/

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void solve(int, int)':
joi2019_ho_t5.cpp:60: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]
   60 |             while(it != uni.size() && uni[it].first <= h){
      |                   ~~~^~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:275:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  275 |         printf("%d\n",ans[i]);
      |                 ~^    ~~~~~~
      |                  |         |
      |                  int       long long int
      |                 %lld
joi2019_ho_t5.cpp:207:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:208:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:211:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:212:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:221:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  221 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void solve(int, int)':
joi2019_ho_t5.cpp:115:18: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |             solve(special,max(pa,pa1));
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:47:13: warning: 'child' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |             if(j == child || j == parent[i]) continue;
      |             ^~

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