oj.uz

Submission #764615

# Submission time Handle Problem Language Result Execution time Memory
764615 2023-06-23T16:32:45 Z raysh07 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 42380 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

struct edge{
    int u, v, w;
};

bool comp(edge x, edge y){
    return x.w < y.w;
}
 
int n, m;
const int maxn = 1e5 + 69;
vector <pair<int, int>> adj[maxn];
int root[maxn], mn[maxn];
set <pair<int, pair<int, int>>> path, ans;
edge e[2 * maxn];
int mp[maxn];

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

bool unite(int x, int y){
    x = find(x); y = find(y);
    if (x == y) return false;
    
    root[y] = x;
    return true;
}

pair<int, pair<int, int>> get(int u, int v, int w){
    return {w, {u, v}};
}

void dfs(int u, int need, int par){
    if (need == u) ans = path;
    
    for (auto [v, w] : adj[u]){
        if (v == par) continue;
        path.insert(get(u, v, w));
        path.insert(get(v, u, w));
        dfs(v, need, u);
        path.erase(get(u, v, w));
        path.erase(get(v, u, w));
    }
}
 
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    m = M;
    vector <pair<int, pair<int, int>>> vec;
    for (int i = 0; i < m; i++){
        vec.push_back({W[i], {U[i], V[i]}});
    }
    sort(vec.begin(), vec.end());
    
    for (int i = 0; i < m; i++){
        e[i].u = vec[i].second.first; 
        e[i].v = vec[i].second.second; 
        e[i].w = vec[i].first;
    }
    
    for (int i = 0; i < n; i++){
        root[i] = i;
        mn[i] = 1e9 + 1;
    }
    
    for (int i = 0; i < m; i++){
        auto x = e[i];
      //  cout << x.u << " " << x.v << "BRUH\n";
        if (unite(x.u, x.v)){
            adj[x.u].push_back({x.v, x.w});
            adj[x.v].push_back({x.u, x.w});
           // cout << "ADDED " << x.u << " " << x.v << " " << x.w << "\n";
        } else {
            mn[x.u] = min(mn[x.u], x.w);
            mn[x.v] = min(mn[x.v], x.w);
        }
    }
}
 
int getMinimumFuelCapacity(int x, int y) {
    dfs(x, y, -1);
    for (int i = 0; i < n; i++) mp[i] = 0;
    int lol = 0;
    for (auto x : ans) {
        lol = max(lol, x.first);
        mp[x.second.first]++;
        mp[x.second.second]++;
    }
    int l1 = 1e9 + 1;
    
    // cout << ans.size() << "\n";
    // for (auto x : ans) {
    //     cout << x.first << " " << x.second.first << " " << x.second.second << "\n";
    // }
    
    for (int i = 0; i < m; i++){
        if (ans.find(get(e[i].u, e[i].v, e[i].w)) == ans.end()){
            if (mp[e[i].u] && mp[e[i].v]) l1 = min(l1, e[i].w);
            else if (e[i].u == x || e[i].u == y || e[i].v == x || e[i].v == y);
            else if (mp[e[i].u] || mp[e[i].v]) l1 = min(l1, e[i].w);
        }
    }
    
    if (l1 > 1e9) return -1;
    else return max(l1, lol);
}

// int main(){
//     int n, m; cin >> n >> m;
//     vector <int> u(m), v(m), w(m);
//     for (auto &x : u) cin >> x;
//     for (auto &x : v) cin >> x;
//     for (auto &x : w) cin >> x;
//     init(n, m, u, v, w);
//     int q; cin >> q;
//     while (q--){
//         int x, y; cin >> x >> y;
//         cout << getMinimumFuelCapacity(x, y) << "\n";
//     }
//     return 0;
// }

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 4 ms 3028 KB Output is correct
7 Correct 4 ms 3028 KB Output is correct
8 Correct 4 ms 3028 KB Output is correct
9 Correct 199 ms 32028 KB Output is correct
10 Correct 464 ms 34552 KB Output is correct
11 Correct 553 ms 41884 KB Output is correct
12 Correct 631 ms 41544 KB Output is correct
13 Correct 290 ms 42380 KB Output is correct
14 Execution timed out 2063 ms 36040 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Execution timed out 2072 ms 12944 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 4 ms 3028 KB Output is correct
7 Correct 4 ms 3028 KB Output is correct
8 Correct 4 ms 3028 KB Output is correct
9 Incorrect 2 ms 2664 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 4 ms 3028 KB Output is correct
7 Correct 4 ms 3028 KB Output is correct
8 Correct 4 ms 3028 KB Output is correct
9 Correct 199 ms 32028 KB Output is correct
10 Correct 464 ms 34552 KB Output is correct
11 Correct 553 ms 41884 KB Output is correct
12 Correct 631 ms 41544 KB Output is correct
13 Correct 290 ms 42380 KB Output is correct
14 Execution timed out 2063 ms 36040 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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