Submission #963888

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963888	2024-04-16T01:53:41 Z	huutuan	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	1379 ms	44464 KB

reconstruction

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct DSURollback{
   vector<int> lab;
   int cc;
   void init(int n){
      lab.assign(n+1, -1);
      cc=n;
   }
   int find_set(int u){
      return lab[u]<0?u:find_set(lab[u]);
   }
   bool union_sets(int u, int v){
      u=find_set(u); v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
         --cc;
         return 1;
      }
      return 0;
   }
   bool same(int u, int v){
      return find_set(u)==find_set(v);
   }
} dsu;

struct Edge{
   int u, v, w;
   Edge (int _u=0, int _v=0, int _w=0){
      u=_u, v=_v, w=_w;
   }
   bool operator<(const Edge &b){
      return make_tuple(w, u, v)<make_tuple(b.w, b.u, b.v);
   }
};

const int N=510, M=1e5+10, Q=1e6+10;
int n, m, q, nxt[M];
Edge a[M];
int b[Q];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=m; ++i) cin >> a[i].u >> a[i].v >> a[i].w;
   dsu.init(n);
   sort(a+1, a+m+1);
   cin >> q;
   for (int i=1; i<=q; ++i) cin >> b[i];
   vector<pair<int, pair<int, int>>> v;
   for (int i=1; i<=m; ++i){
      dsu.init(n);
      int j;
      for (j=i+1; j<=m; ++j){
         dsu.union_sets(a[j].u, a[j].v);
         if (dsu.same(a[i].u, a[i].v)) break;
      }
      int rval=j==m+1?1e9:a[i].w+(a[j].w-a[i].w+1)/2;
      dsu.init(n);
      for (j=i-1; j>=1; --j){
         dsu.union_sets(a[j].u, a[j].v);
         if (dsu.same(a[i].u, a[i].v)) break;
      }
      int lval=j==0?-1:a[i].w-(a[i].w-a[j].w)/2;
      v.push_back({lval, {i, 1}});
      v.push_back({a[i].w, {i, 2}});
      v.push_back({rval, {i, 3}});
   }
   sort(v.begin(), v.end());
   int add=0, mul=0;
   for (int i=1, j=0; i<=q; ++i){
      while (j<(int)v.size() && v[j].first<=b[i]){
         if (v[j].second.second==1){
            add+=a[v[j].second.first].w;
            mul-=1;
         }else if (v[j].second.second==2){
            add-=a[v[j].second.first].w*2;
            mul+=2;
         }else{
            add+=a[v[j].second.first].w;
            mul-=1;
         }
         ++j;
      }
      cout << add+mul*b[i] << '\n';
   }
   return 0;
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Incorrect	1 ms	4444 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Incorrect	1 ms	4444 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1339 ms	41020 KB	Output is correct
5	Correct	1379 ms	40968 KB	Output is correct
6	Correct	1338 ms	40840 KB	Output is correct
7	Correct	668 ms	42948 KB	Output is correct
8	Correct	448 ms	44464 KB	Output is correct
9	Correct	368 ms	42408 KB	Output is correct
10	Correct	1311 ms	40608 KB	Output is correct
11	Correct	445 ms	44324 KB	Output is correct