Submission #747291

#	Time	Username	Problem	Language	Result	Execution time	Memory
747291		Paul_Liao_1457	Reconstruction Project (JOI22_reconstruction)	C++17	77 / 100	5002 ms	59284 KiB

reconstruction

#define LOCAL
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>

#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=b;i>=a;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

int boss[505];

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

void merge(int a, int b) {
    if(a == b) return;
    boss[a] = b;
}

signed main() {

    AC;

    int n, m;
    cin >> n >> m;

    vector<pair<int, pair<int, int>>> v;

    FOR(i, 0, m) {
        int a, b, w;
        cin >> a >> b >> w;
        v.pb(mp(w, mp(a, b)));
    }

    int q;
    cin >> q;

    vector<pair<pair<int,  bool>, pair<int, int>>> op;
    
    FOR(i, 0, q) {
        int x; cin >> x;
        op.pb(mp(mp(x, 0), mp(0,0)));
    }
    
    //cout << "hi1" << endl;

    sort(v.begin(), v.end());

    multiset<int> cur;

    FOR(i, 0, m) {
        FOR(i, 1, n+1) boss[i] = i;

        int now = i - 1;
        while (now >= 0) {
            merge(find(v[now].S.F), find(v[now].S.S));
            if(find(v[i].S.F) == find(v[i].S.S)) break;
            now--;
        }

        if (now < 0) {
            cur.insert(v[i].F);        
        } else {
            op.pb(mp(mp((v[i].F + v[now].F)/2, 1), mp(v[now].F, v[i].F)));
        }
    }

    sort(op.begin(), op.end());

    vector<ll> ans;

    FOR(i, 0, op.size()) {
         if (!op[i].F.S) {
            ll sum = 0;
            for (auto j:cur) sum += abs(j - op[i].F.F);
            ans.pb(sum);
         } else {
            cur.erase(cur.find(op[i].S.F));
            cur.insert(op[i].S.S);
         }
    }

    //cout << "hi" << endl;
    
    FOR(i, 0, ans.size()) cout << ans[i] << endl;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:19:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, bool>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i,a,b) for(int i=a;i<b;i++)
......
   93 |     FOR(i, 0, op.size()) {
      |         ~~~~~~~~~~~~~~~          
reconstruction.cpp:93:5: note: in expansion of macro 'FOR'
   93 |     FOR(i, 0, op.size()) {
      |     ^~~
reconstruction.cpp:19:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i,a,b) for(int i=a;i<b;i++)
......
  106 |     FOR(i, 0, ans.size()) cout << ans[i] << endl;
      |         ~~~~~~~~~~~~~~~~         
reconstruction.cpp:106:5: note: in expansion of macro 'FOR'
  106 |     FOR(i, 0, ans.size()) cout << ans[i] << endl;
      |     ^~~

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