Submission #1263460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263460		minhpk	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1116 ms	20776 KiB

reconstruction

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
struct node{
      int x,y,val;
};
node z[1000005];
bool cmp(node a,node b){
     return a.val<b.val;
}
bool cmp1(node a,node b){
     return a.x<b.x;
}
vector <node> event;
int cnt[1000005];
int inf=1e16;
set<pair<int,int>> v[1005];
void dfs(int i,int par){
     for (auto [p,w]:v[i]){
          if (p==par){
              continue;
          }
          cnt[p]=min(cnt[i],w);
          dfs(p,i);
     }
}

void add(int x,int y,int val){
    v[x].insert({y,val});
    v[y].insert({x,val});
}
void del(int x,int y,int val){
    auto it=v[x].find({y,val});
    v[x].erase(it);

    auto it1=v[y].find({x,val});
    v[y].erase(it1);
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=b;i++){
         cin >> z[i].x >> z[i].y >> z[i].val;
    }
    sort(z+1,z+1+b,cmp);
    for (int i=1;i<=b;i++){

         auto [x,y,w]=z[i];
         for (int j=1;j<=a;j++){
              cnt[j]=inf;
         }
//         cerr << x << " " << y << " " << w << " ";
         dfs(x,x);
//         cerr << "ok" << "\n";
         if (cnt[y]!=inf){
             int pos=cnt[y];
             auto [u,v,c]=z[pos];
             int mid=(c+w+1)/2;
             event.push_back({mid,c+w,-2});
             del(u,v,pos);
         }else{
             event.push_back({0,w,-1});
         }
         event.push_back({w,-2*w,2});
         add(x,y,i);
    }
    sort(event.begin(),event.end(),cmp1);
    int cur=0;
    int num1=0,num2=0;
    int q;
    cin >> q;
    while (q--){
         int x;
         cin >> x;
         while (cur<event.size() && event[cur].x<=x){
               num1+=event[cur].y;
               num2+=event[cur].val;
               cur++;
         }
         cout << num2*x +num1 << "\n";
    }
    return 0;
}

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