Submission #912360

#	Time	Username	Problem	Language	Result	Execution time	Memory
912360		hamidh100	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	1545 ms	25564 KiB

reconstruction

/* In the name of God */

#include <bits/stdc++.h>
//#pragma GCC optimize("O2,O3,Ofast,unroll-loops")
//#pragma GCC target("avx")

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 998244353;

inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 505;

int par[MAXN];

int gp(int v){
    return (par[v] == v ? v : par[v] = gp(par[v]));
}

ll mst = 0;
void merge(int u, int v, int e){
    u = gp(u), v = gp(v);
    if (u == v) return;
    mst += e;
    par[u] = v;
}

VI vec[MAXN];
int pt[MAXN];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        vec[min(u, v)].PB(w);
    }
    for (int i = 1; i < n; i++) sort(all(vec[i]));
    int q; cin >> q;
    while (q--){
        int x; cin >> x;
        ll ans = 0;
        for (int i = 1; i < n; i++){
            int cur = abs(x - vec[i][pt[i]]);
            while (1){
                if (pt[i] == vec[i].size() - 1) break;
                int val = vec[i][pt[i] + 1];
                if (abs(x - val) < cur){
                    pt[i]++;
                    cur = abs(x - val);
                }
                else break;
            }
            ans += cur;
        }
        cout << ans << endl;
    }
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 if (pt[i] == vec[i].size() - 1) break;
      |                     ~~~~~~^~~~~~~~~~~~~~~~~~~~

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