Submission #556667

#	Time	Username	Problem	Language	Result	Execution time	Memory
556667		600Mihnea	Reconstruction Project (JOI22_reconstruction)	C++17	3 / 100	32 ms	4668 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[N];
int biggest[N];

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);
  }
  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;

  }
  cin>>q;
  for (int iq=1;iq<=q;iq++) {
    int w;
    cin>>w;
    ll sol=0;
    for(int i=1;i<=m;i++) {
      if (smallest[i]<=w&&w<=biggest[i]) {
        sol+=abs(edges[i].w-w);
      }
    }
    cout<<sol<<"\n";
  }
}
/**
1 : -1 4
2 : -1 5
3 : 4 7
4 : -1 11
5 : 5 9
6 : -1 10
7 : 7 1000000001
8 : 9 1000000001
9 : 10 1000000001
10 : 11 1000000001
**/

Compilation message (stderr)

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

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