Submission #565199

#	Time	Username	Problem	Language	Result	Execution time	Memory
565199		jeff	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	758 ms	32048 KiB

reconstruction

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

pair<long long, pair<long long, long long> > A[100000], l;
vector<pair<long long, pair<long long, long long> > > s;
vector<pair<long long, long long> > adj[500], f;
pair<long long, long long> r;
bool vt[500];

bool it(long long i, long long t) {
    if (i == t) return 1;
    if (vt[i]) return 0;
    vt[i] = 1;
    for (long long j = 0; j < adj[i].size(); ++j) if (it(adj[i][j].first, t)) {
        l = min(l, make_pair(adj[i][j].second, make_pair(i, adj[i][j].first)));
        return 1;
    }
    return 0;
}

int main() {
    long long N, M, Q, x, i, j;
    scanf("%lld %lld", &N, &M);
    for (i = 0; i < M; ++i) scanf("%lld %lld %lld", &A[i].second.first, &A[i].second.second, &A[i].first), --A[i].second.first, --A[i].second.second;
    sort(A, A + M);
    for (i = 0; i < M; ++i) {
        l = make_pair(LLONG_MAX, make_pair(-1, -1));
        memset(vt, 0, sizeof(vt));
        if (it(A[i].second.first, A[i].second.second)) {
            for (j = 0; j < adj[l.second.first].size(); ++j) if (adj[l.second.first][j].first != l.second.second) f.push_back(adj[l.second.first][j]);
            swap(adj[l.second.first], f);
            f.clear();
            for (j = 0; j < adj[l.second.second].size(); ++j) if (adj[l.second.second][j].first != l.second.first) f.push_back(adj[l.second.second][j]);
            swap(adj[l.second.second], f);
            f.clear();
            s.emplace_back((l.first + A[i].first + 1) / 2, make_pair(-2, l.first + A[i].first));
            s.emplace_back(A[i].first, make_pair(2, -A[i].first * 2));
            adj[A[i].second.first].emplace_back(A[i].second.second, A[i].first);
            adj[A[i].second.second].emplace_back(A[i].second.first, A[i].first);
        } else {
            r.first -= 1;
            r.second += A[i].first;
            s.emplace_back(A[i].first, make_pair(2, -A[i].first * 2));
            adj[A[i].second.first].emplace_back(A[i].second.second, A[i].first);
            adj[A[i].second.second].emplace_back(A[i].second.first, A[i].first);
        }
    }
    sort(s.begin(), s.end());
    scanf("%lld", &Q);
    for (i = j = 0; i < Q; ++i) {
        scanf("%lld", &x);
        for (j; j < s.size() && s[j].first <= x; ++j) r.first += s[j].second.first, r.second += s[j].second.second;
        printf("%lld\n", r.first * x + r.second);
    }
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'bool it(long long int, long long int)':
reconstruction.cpp:14:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (long long j = 0; j < adj[i].size(); ++j) if (it(adj[i][j].first, t)) {
      |                           ~~^~~~~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:30:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for (j = 0; j < adj[l.second.first].size(); ++j) if (adj[l.second.first][j].first != l.second.second) f.push_back(adj[l.second.first][j]);
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:33:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for (j = 0; j < adj[l.second.second].size(); ++j) if (adj[l.second.second][j].first != l.second.first) f.push_back(adj[l.second.second][j]);
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:52:14: warning: statement has no effect [-Wunused-value]
   52 |         for (j; j < s.size() && s[j].first <= x; ++j) r.first += s[j].second.first, r.second += s[j].second.second;
      |              ^
reconstruction.cpp:52:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (j; j < s.size() && s[j].first <= x; ++j) r.first += s[j].second.first, r.second += s[j].second.second;
      |                 ~~^~~~~~~~~~
reconstruction.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%lld %lld", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:24:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     for (i = 0; i < M; ++i) scanf("%lld %lld %lld", &A[i].second.first, &A[i].second.second, &A[i].first), --A[i].second.first, --A[i].second.second;
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%lld", &Q);
      |     ~~~~~^~~~~~~~~~~~
reconstruction.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%lld", &x);
      |         ~~~~~^~~~~~~~~~~~

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