Submission #1141082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141082		salmon	Tourism (JOI23_tourism)	C++20	100 / 100	742 ms	17868 KiB

tourism

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

int N;
int M;
int Q;
int a,b;
vector<int> adjlst[100100];
int d[100100];
int sise[100100];
int parent[100100];
int dparent[100100];
int pre[100100];
int post[100100];
int cont = 0;
int lst[100100];
map<pair<int,int>,int> mep;
vector<pair<pair<int,int>,int>> queries;
int l,r;
int ans[100100];
int ft[100100];
int invpre[100100];

void update(int i, int k){
    while(i <= M){
        ft[i] += k;
        i += (i&(-i));
    }
}

int query(int i){
    long long int V = 0;
    while(i != 0){
        V += ft[i];
        i -= (i&(-i));
    }
    return V;
}

void fs(int i, int p, int de){
    d[i] = de;
    sise[i] = 1;
    parent[i] = p;

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

void dfs(int i){
    pre[i] = cont;
    cont++;

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

    for(int j : adjlst[i]){
        if(j == parent[i]) continue;
        ii = max(ii,{sise[j],j});
    }

    if(ii.second != -1){
        dparent[ii.second] = dparent[i];
        dfs(ii.second);

        for(int j : adjlst[i]){
            if(j == parent[i]) continue;
            if(j == ii.second) continue;
            dparent[j] = j;
            dfs(j);
        }
    }

    post[i] = cont - 1;
}

void donk(int a, int b, int c){
    while(dparent[a] != dparent[b]){
        if(d[dparent[a]] < d[dparent[b]]){
            swap(a,b);
        }
        pair<int,int> ii = {pre[dparent[a]],pre[a]};

        while(true){
            auto it = mep.lower_bound({pre[dparent[a]] + 1, -1 });

            if(it == mep.end()) break;
            if( (it -> first).first > pre[a]) break;

            if((it -> first).second <= pre[a]){
                update(it -> second,-((it->first).second - (it->first).first + 1) );
                mep.erase(it);
            }
            else{
                update(it -> second,-(pre[a] - (it->first).first + 1) );
                mep[{pre[a] + 1, (it -> first).second}] = it->second;
                mep.erase(it);
                break;
            }
        }

        while(true){
            auto it = mep.lower_bound({ii.first + 1, -1 });

            if(it == mep.begin()) break;

            advance(it,-1);

            if((it -> first).second < ii.first) break;

            if((it -> first).second >= ii.second){
                update(it -> second,-(ii.second - ii.first + 1));
                if((it->first).first < ii.first) mep.insert({{(it->first).first, ii.first - 1 },it -> second});
                if(ii.second < (it->first).second ) mep.insert({{ii.second + 1, (it->first).second},it -> second});
                mep.erase(it);
            }
            else if((it-> first).first >= ii.first){
                update(it -> second,-((it->first).second - (it->first).first + 1) );
                mep.erase(it);
            }
            else{
                update(it -> second,-((it->first).second - ii.first + 1) );
                mep[{(it -> first).first, ii.first - 1}] = it->second;
                mep.erase(it);
                break;
            }
        }

        mep.insert({ii,c});
        update(c,ii.second - ii.first + 1);
        a = parent[dparent[a]];
    }
    pair<int,int> ii = {min(pre[a],pre[b]),max(pre[a],pre[b])};

     while(true){
        auto it = mep.lower_bound({ii.first + 1, -1 });

        if(it == mep.end()) break;
        if( (it -> first).first > ii.second) break;

        if((it -> first).second <= ii.second){
            update(it -> second,-((it->first).second - (it->first).first + 1) );
            mep.erase(it);
        }
        else{
            update(it -> second,-(ii.second - (it->first).first + 1) );
            mep[{ii.second + 1, (it -> first).second}] = it->second;
            mep.erase(it);
            break;
        }
    }

    while(true){
        auto it = mep.lower_bound({ii.first + 1, -1 });

        if(it == mep.begin()) break;

        advance(it,-1);

        if((it -> first).second < ii.first) break;

        if((it -> first).second > ii.second){
            update(it -> second,-(ii.second - ii.first + 1));
            if((it->first).first < ii.first) mep.insert({{(it->first).first, ii.first - 1 },it -> second});
            if(ii.second < (it->first).second ) mep.insert({{ii.second + 1, (it->first).second},it->second});
            mep.erase(it);
        }
        else if((it-> first).first >= ii.first){
            update(it -> second,-((it->first).second - (it->first).first + 1) );
            mep.erase(it);
        }
        else{
            update(it -> second,-((it->first).second - ii.first + 1) );
            mep[{(it -> first).first, ii.first - 1}] = it->second;
            mep.erase(it);
            break;
        }
    }

    mep.insert({ii,c});
    update(c,ii.second - ii.first + 1);
}

int main(){

    scanf(" %d",&N);

    scanf(" %d",&M);

    scanf(" %d",&Q);

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

        adjlst[a].push_back(b);
        adjlst[b].push_back(a);
    }

    fs(1, -1, 0);
    dparent[1] = 1;
    dfs(1);

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

    for(int i = 1; i <= Q; i++){
        scanf(" %d",&l);
        scanf(" %d",&r);

        queries.push_back({{l,r},i});
    }

    sort(queries.begin(),queries.end(), greater<pair<pair<int,int>,int>>());

    auto it = M - 1;

    for(int i = 0; i < Q; i++){
        //printf("e: %d\n",queries[i].first.first);
        while(it >= queries[i].first.first){
            donk(lst[it],lst[it + 1],it + 1);
            /*for(pair<pair<int,int>,int> ii : mep){
                printf("%d %d %d\n",ii.first.first,ii.first.second,ii.second);
            }
            printf("f %d\n",it);
            printf("\n");*/
            it--;
        }

        if(queries[i].first.first != queries[i].first.second) ans[queries[i].second] = query(queries[i].first.second);
        else ans[queries[i].second] = 1;
    }

    for(int i = 1; i <= Q; i++) printf("%d\n",ans[i]);
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:186:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
tourism.cpp:188:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
tourism.cpp:190:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
tourism.cpp:193:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |         scanf(" %d",&a);
      |         ~~~~~^~~~~~~~~~
tourism.cpp:194:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |         scanf(" %d",&b);
      |         ~~~~~^~~~~~~~~~
tourism.cpp:205:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
tourism.cpp:210:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |         scanf(" %d",&l);
      |         ~~~~~^~~~~~~~~~
tourism.cpp:211:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |         scanf(" %d",&r);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41