oj.uz

Submission #556667

# Submission time Handle Problem Language Result Execution time Memory
556667 2022-05-03T13:55:17 Z 600Mihnea Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 32 ms 4668 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Runtime error 32 ms 4428 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Runtime error 32 ms 4668 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Runtime error 1 ms 576 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Runtime error 32 ms 4428 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Runtime error 32 ms 4428 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -