Submission #556250

#	Time	Username	Problem	Language	Result	Execution time	Memory
556250		600Mihnea	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5051 ms	4748 KiB

reconstruction

#include <bits/stdc++.h>

bool home = 1;

using namespace std;

typedef long long ll;

int wglob;

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

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

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

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

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;
  }
  cin>>q;

  for (int iq=1;iq<=q;iq++) {
    int w;
    cin>>w;
    wglob=w;
    sort(edges+1,edges+m+1);
    for (int i=1;i<=n;i++) t[i]=i;
    ll sol=0;
    for (int i=1;i<=m;i++) {
      int a=edges[i].a;
      int b=edges[i].b;
      int cost=abs(wglob-edges[i].w);
      if (root(a)!=root(b)) {
        join(a,b);
        sol+=cost;
      }
    }
    cout<<sol<<"\n";
  }
}

Compilation message (stderr)

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

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