oj.uz

Submission #568892

# Submission time Handle Problem Language Result Execution time Memory
568892 2022-05-26T10:11:12 Z tqbfjotld Reconstruction Project (JOI22_reconstruction) C++14
42 / 100
 807 ms 34840 KB 
#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][300005];

void upd(int pos, int val, int id){
    pos++;
    while (pos<300005){
        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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 629 ms 8860 KB Output is correct
21 Correct 330 ms 8796 KB Output is correct
22 Correct 418 ms 8860 KB Output is correct
23 Correct 512 ms 8672 KB Output is correct
24 Correct 527 ms 8376 KB Output is correct
25 Correct 616 ms 8416 KB Output is correct
26 Correct 652 ms 8412 KB Output is correct
27 Correct 618 ms 8348 KB Output is correct
28 Correct 671 ms 8364 KB Output is correct
29 Correct 387 ms 7204 KB Output is correct
30 Correct 618 ms 8192 KB Output is correct
31 Correct 648 ms 8212 KB Output is correct
32 Correct 657 ms 8440 KB Output is correct
33 Correct 602 ms 7696 KB Output is correct
34 Correct 244 ms 6836 KB Output is correct
35 Correct 597 ms 7664 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Runtime error 807 ms 34840 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Runtime error 240 ms 31704 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 629 ms 8860 KB Output is correct
21 Correct 330 ms 8796 KB Output is correct
22 Correct 418 ms 8860 KB Output is correct
23 Correct 512 ms 8672 KB Output is correct
24 Correct 527 ms 8376 KB Output is correct
25 Correct 616 ms 8416 KB Output is correct
26 Correct 652 ms 8412 KB Output is correct
27 Correct 618 ms 8348 KB Output is correct
28 Correct 671 ms 8364 KB Output is correct
29 Correct 387 ms 7204 KB Output is correct
30 Correct 618 ms 8192 KB Output is correct
31 Correct 648 ms 8212 KB Output is correct
32 Correct 657 ms 8440 KB Output is correct
33 Correct 602 ms 7696 KB Output is correct
34 Correct 244 ms 6836 KB Output is correct
35 Correct 597 ms 7664 KB Output is correct
36 Correct 631 ms 8724 KB Output is correct
37 Correct 304 ms 8764 KB Output is correct
38 Correct 456 ms 8804 KB Output is correct
39 Correct 541 ms 8824 KB Output is correct
40 Correct 571 ms 8704 KB Output is correct
41 Correct 663 ms 8828 KB Output is correct
42 Correct 633 ms 8684 KB Output is correct
43 Correct 637 ms 8804 KB Output is correct
44 Correct 643 ms 8724 KB Output is correct
45 Correct 393 ms 7088 KB Output is correct
46 Correct 627 ms 8776 KB Output is correct
47 Correct 643 ms 8792 KB Output is correct
48 Correct 688 ms 8696 KB Output is correct
49 Correct 637 ms 8088 KB Output is correct
50 Correct 275 ms 6900 KB Output is correct
51 Correct 643 ms 7708 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 629 ms 8860 KB Output is correct
21 Correct 330 ms 8796 KB Output is correct
22 Correct 418 ms 8860 KB Output is correct
23 Correct 512 ms 8672 KB Output is correct
24 Correct 527 ms 8376 KB Output is correct
25 Correct 616 ms 8416 KB Output is correct
26 Correct 652 ms 8412 KB Output is correct
27 Correct 618 ms 8348 KB Output is correct
28 Correct 671 ms 8364 KB Output is correct
29 Correct 387 ms 7204 KB Output is correct
30 Correct 618 ms 8192 KB Output is correct
31 Correct 648 ms 8212 KB Output is correct
32 Correct 657 ms 8440 KB Output is correct
33 Correct 602 ms 7696 KB Output is correct
34 Correct 244 ms 6836 KB Output is correct
35 Correct 597 ms 7664 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 328 KB Output is correct
39 Runtime error 807 ms 34840 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -