Submission #596790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
596790	2022-07-15T05:13:28 Z	반딧불(#8447)	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	1687 ms	27648 KB

reconstruction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct unionFind{
    int par[1002];

    void init(int _n){
        for(int i=1; i<=_n; i++) par[i] = i;
    }

    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

struct Edge{
    int x, y; ll w;
    Edge(){}
    Edge(int x, int y, ll w): x(x), y(y), w(w){}
    bool operator<(const Edge &r)const{
        return w>r.w;
    }
};

int n, m, q;
vector<ll> vec[502];
int pnt[502];
Edge arr[100002];

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d %d %lld", &arr[i].x, &arr[i].y, &arr[i].w);
        vec[arr[i].x].push_back(arr[i].w);
    }
    for(int i=1; i<=n; i++){
        vec[i].push_back(-1e18);
        sort(vec[i].begin(), vec[i].end());
        vec[i].push_back(1e18);
    }
    scanf("%d", &q);
    while(q--){
        ll tmp;
        scanf("%lld", &tmp);
        ll ans = 0;
        for(int i=1; i<n; i++){
            while(vec[i][pnt[i]] < tmp) pnt[i]++;
            ans += min(tmp - vec[i][pnt[i]-1], vec[i][pnt[i]] - tmp);
        }
        printf("%lld\n", ans);
    }
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
reconstruction.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d %d %lld", &arr[i].x, &arr[i].y, &arr[i].w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
reconstruction.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%lld", &tmp);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1584 ms	23624 KB	Output is correct
5	Correct	1687 ms	25316 KB	Output is correct
6	Correct	1632 ms	25304 KB	Output is correct
7	Correct	1484 ms	27236 KB	Output is correct
8	Correct	1332 ms	27648 KB	Output is correct
9	Correct	1286 ms	27236 KB	Output is correct
10	Correct	1628 ms	25664 KB	Output is correct
11	Correct	1315 ms	27600 KB	Output is correct