oj.uz

Submission #754622

# Submission time Handle Problem Language Result Execution time Memory
754622 2023-06-08T07:11:05 Z otarius Stove (JOI18_stove) C++17
0 / 100
 2 ms 2644 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -