Submission #568727

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
568727	2022-05-26T06:35:39 Z	joelau	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	1895 ms	38396 KB

reconstruction

#include <bits/stdc++.h>
using namespace std;

long long N,M,Q, ans[1000005];
pair<long long,long long> queries[1000005];
vector<long long> lst[505];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    for (long long i = 0; i < M; ++i) {
        long long u,v,w; cin >> u >> v >> w; u--, v--;
        lst[u].push_back(w);
    }
    for (long long i = 0; i < N; ++i) sort(lst[i].begin(),lst[i].end());
    cin >> Q;
    for (long long i = 0; i < Q; ++i) {
        cin >> queries[i].first;
        queries[i].second = i;
    }
    sort(queries,queries+Q);
    memset(ans,0,sizeof(ans));
    for (long long i = 0; i < N-1; ++i) {
        for (long long j = 0, k = 0; j < Q; ++j) {
            while (k < lst[i].size() && lst[i][k] < queries[j].first) k++;
            long long x = 4e18;
            if (k != lst[i].size()) x = min(x,lst[i][k]-queries[j].first);
            if (k != 0) x = min(x,queries[j].first-lst[i][k-1]);
            ans[queries[j].second] += x;
        }
    }
    for (long long i = 0; i < Q; ++i) cout << ans[i] << '\n';

    return 0;
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:25:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |             while (k < lst[i].size() && lst[i][k] < queries[j].first) k++;
      |                    ~~^~~~~~~~~~~~~~~
reconstruction.cpp:27:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             if (k != lst[i].size()) x = min(x,lst[i][k]-queries[j].first);
      |                 ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	8148 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	5 ms	8148 KB	Output is correct
2	Correct	4 ms	8140 KB	Output is correct
3	Correct	4 ms	8148 KB	Output is correct
4	Correct	1835 ms	35916 KB	Output is correct
5	Correct	1822 ms	36268 KB	Output is correct
6	Correct	1822 ms	36244 KB	Output is correct
7	Correct	1836 ms	38172 KB	Output is correct
8	Correct	1833 ms	38392 KB	Output is correct
9	Correct	1840 ms	38044 KB	Output is correct
10	Correct	1763 ms	36208 KB	Output is correct
11	Correct	1895 ms	38396 KB	Output is correct