Submission #754622

#	Time	Username	Problem	Language	Result	Execution time	Memory
754622		otarius	Stove (JOI18_stove)	C++17	0 / 100	2 ms	2644 KiB

stove

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

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pii pair<int, int>
const ll mod = 1e9 + 7;

vector<pii> G[100005];
int x, y, n, m, par[100005], s, e;
void make_set() {
    for (int i = 1; i <= n; i++)
        par[i] = i;
}
int find_set(int v) {
    if (par[v] == v)
        return v;
    return par[v] = find_set(par[v]);
}
bool union_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        par[b] = a;
        return true;
    } return false;
}
void dfs(int v, int par, int cur) {
    if (v == e) {
        cout << cur;
        return;
    } for (auto u : G[v])
        if (u.ff != par) dfs(u.ff, v, max(cur, u.sc));
}
void solve() {
    cin >> n >> m;
    make_set();
    cin >> s >> e;
    vector<pii> edj;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        edj.pb({x, y});
    } int val[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    set<pair<int, pii>> st;
    for (auto v : edj)
        st.insert({abs(val[v.ff] - val[v.sc]), v});
    for (auto v : st) {
        if (union_set(v.sc.ff, v.sc.sc)) {
            G[v.sc.ff].pb({v.sc.sc, v.ff}); G[v.sc.sc].pb({v.sc.ff, v.ff});
        }
    } dfs(s, -1, -1);
}
int main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50