Submission #556669

#	Time	Username	Problem	Language	Result	Execution time	Memory
556669		600Mihnea	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	2383 ms	33860 KiB

reconstruction

#include <bits/stdc++.h>

bool home = 1;

using namespace std;

typedef long long ll;

struct Edge{
  int a;
  int b;
  int w;
};

bool operator < (Edge a,Edge b) {
  return a.w<b.w;
}

const int N=500+7;
const int M=100000+7;
const int Q=1000000+7;
const int INF=(int)1e9+7;
int n;
int m;
int q;
int t[N];
Edge edges[M];

void clr() {
  for(int i=1;i<=n;i++) t[i]=i;
}

int root(int a) {
  if (t[a]==a) return a;
  return t[a]=root(t[a]);
}

void join(int a,int b) {
  t[root(a)]=root(b);
}

int smallest[M];
int biggest[M];

struct E{
  ll t,a,b;
};

bool operator<(E a,E b) {
  return a.t<b.t;
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif

  home=0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }

  cin>>n>>m;
  for (int i=1;i<=m;i++) {
    cin>>edges[i].a>>edges[i].b>>edges[i].w;
    smallest[i]=-INF;
    biggest[i]=+INF;
  }
  sort(edges+1,edges+m+1);

  for (int i=2;i<=m;i++){
    assert(edges[i-1].w<=edges[i].w);
  }

  vector<E> e;

  for (int i=1;i<=m;i++) {

    clr();

    int low=i-1;
    while (low>=1&&root(edges[i].a)!=root(edges[i].b)) {
      join(edges[low].a,edges[low].b);
      low--;
    }

    if(root(edges[i].a)==root(edges[i].b)) low++;

    clr();

    int high=i+1;
    while(high<=m&&root(edges[i].a)!=root(edges[i].b)) {
      join(edges[high].a,edges[high].b);
      high++;
    }


    if(root(edges[i].a)==root(edges[i].b)) high--;

    if (low>=1) smallest[i]=(edges[low].w+edges[i].w+1)/2;
    if (high<=m) biggest[i]=(edges[high].w+edges[i].w-1)/2;

    e.push_back({smallest[i], +1, -edges[i].w});
    e.push_back({edges[i].w, -2, 2*edges[i].w});
    e.push_back({biggest[i]+1, +1, -edges[i].w});
  }
  sort(e.begin(),e.end());
  ll a=0,b=0;
  int p=0;
  cin>>q;
  for (int iq=1;iq<=q;iq++) {
    int w;
    cin>>w;
    while(p<(int)e.size()&&e[p].t<=w) {
      a+=e[p].a;
      b+=e[p].b;
      p++;
    }
    cout<<-(a*w+b)<<"\n";
  }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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