Submission #568727

#	Time	Username	Problem	Language	Result	Execution time	Memory
568727		joelau	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	1895 ms	38396 KiB

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 (stderr)

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
• Subtask 2: 0 / 4
• Subtask 3: 7 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23