Submission #568895

#	Time	Username	Problem	Language	Result	Execution time	Memory
568895		tqbfjotld	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1106 ms	60184 KiB

reconstruction

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

set<pair<int,int> > mst[505];

int A[100005];
int B[100005];
int W[100005];

int find_min(int node, int dest, int pa){
    if (node==dest) return -1;
    for (auto x : mst[node]){
        if (x.first==pa) continue;
        int res = find_min(x.first,dest,node);
        if (res!=-2){
            if (res==-1) return x.second;
            if (W[res]<W[x.second]) return res;
            else return x.second;
        }
    }
    return -2;
}

int n;

vector<pair<int,int> > add,del;
const long long INF = 1000000010;
long long fenw[2][1300005];

void upd(int pos, int val, int id){
    pos++;
    while (pos<1300005){
        fenw[id][pos]+=val;
        pos+=(pos&-pos);
    }
}
long long qu(int pos, int id){
    long long ans = 0;
    pos++;
    while (pos>0){
        ans += fenw[id][pos];
        pos -= pos&-pos;
    }
    return ans;
}

long long ans[1000005];
vector<int> discr;

void upd2(int pos, int val, int id){
    int t = lower_bound(discr.begin(),discr.end(),pos)-discr.begin();
    upd(t,val,id);
}
long long qu2(int pos, int id){
    int t = lower_bound(discr.begin(),discr.end(),pos)-discr.begin();
    return qu(t,id);
}

int main(){
    scanf("%d",&n);
    int m;
    scanf("%d",&m);
    vector<pair<int,pair<int,int>>> edgel;
    for (int x = 0; x<m; x++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edgel.push_back({c,{a,b}});
    }
    sort(edgel.begin(),edgel.end());
    for (int x = 0; x<m; x++){
        A[x] = edgel[x].second.first;
        B[x] = edgel[x].second.second;
        W[x] = edgel[x].first;
        discr.push_back(W[x]);
    }
    for (int x = 0; x<m; x++){
        int t = find_min(A[x],B[x],-1);
        if (t==-2){
            add.push_back({-1,x});
            mst[A[x]].insert({B[x],x});
            mst[B[x]].insert({A[x],x});
            continue;
        }
        //printf("swap %d to %d at q %d\n",t,x,(W[x]+W[t])/2);
        del.push_back({(W[x]+W[t])/2,t});
        mst[A[t]].erase(mst[A[t]].lower_bound({B[t],t}));
        mst[B[t]].erase(mst[B[t]].lower_bound({A[t],t}));
        add.push_back({(W[x]+W[t])/2,x});
        mst[A[x]].insert({B[x],x});
        mst[B[x]].insert({A[x],x});
    }
    sort(add.begin(),add.end());
    sort(del.begin(),del.end());

    int q;
    scanf("%d",&q);
    vector<pair<int,int> > queries;
    for (int x = 0; x<q; x++){
        int a;
        scanf("%d",&a);
        queries.push_back({a,x});
        discr.push_back(a);
    }
    sort(discr.begin(),discr.end());
    sort(queries.begin(),queries.end());
    int i1 = 0;
    int i2 = 0;
    for (auto x : queries){
        while (i1<add.size() && x.first>add[i1].first){
            auto t = add[i1];
            upd2(W[t.second],W[t.second],0);
            upd2(W[t.second],1,1);
            //printf("add %d\n",t.second);
            i1++;
        }
        while (i2<del.size() && x.first>del[i2].first){
            auto t = del[i2];
            upd2(W[t.second],-W[t.second],0);
            upd2(W[t.second],-1,1);
            //printf("del %d\n",t.second);
            i2++;
        }
        //printf("qu %d\n",x.first);
        long long sum1 = qu2(x.first,0);
        long long sumtot = qu2(INF-5,0);
        long long num1 = qu2(x.first,1);
        long long numtot = n-1;
        ans[x.second] = num1*x.first-sum1 + (sumtot-sum1)-x.first*(numtot-num1);
    }
    for (int x = 0; x<q; x++){
        printf("%lld\n",ans[x]);
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         while (i1<add.size() && x.first>add[i1].first){
      |                ~~^~~~~~~~~~~
reconstruction.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         while (i2<del.size() && x.first>del[i2].first){
      |                ~~^~~~~~~~~~~
reconstruction.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
reconstruction.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
reconstruction.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
reconstruction.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23