oj.uz

Submission #414224

# Submission time Handle Problem Language Result Execution time Memory
414224 2021-05-30T09:21:27 Z ACmachine Swapping Cities (APIO20_swap) C++17
7 / 100
 226 ms 14412 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i>=(k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const int INF = (int)1e9 + 7;
const ll INFF = (ll)1e18;
int n, m;
vector<vector<array<int, 2>>> merge_history;// ked sa mensi mergne do vacsieho, zapamatam si ze mensi -> merge vacsi; max logn krat sa potom nieco mergne; usortim podla casov;
// when comp became good 
vector<int> good_history;
struct dsu{
    vector<int> p;
    vector<bool> good;
    vector<int> deg;
    int counter = -1;
    dsu(int n){
        deg.resize(n, 0);
        p.resize(n, -1);
        good.resize(n, false);
    }
    int find(int x){
        return (p[x] < 0 ? x : p[x] = find(p[x]));
    }
    bool same_set(int u, int v){
        return find(u) == find(v);
    }
    bool join(int u, int v){
        counter++;
        deg[u]++; deg[v]++; 
        bool dgood = ((deg[u] > 2 || deg[v] > 2) ? true : false);
        u = find(u);
        v = find(v);
        if(u == v){
            if(!good[u]){
                good_history[u] = counter;
                good[u] = true;
            }
            return false;
        } 
        if(-p[u] < -p[v])
            swap(u, v);
        if(!good[u] && (dgood || good[v])){
            good[u] = true;
            good_history[u] = counter;
        }
        p[u] += p[v]; p[v] = u;
        merge_history[v].pb({counter, u});
        return true;
    }
};
vector<array<int, 3>> edges;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N; m = M;
    good_history.resize(n, -1);
    merge_history.resize(n);
    REP(i, m){
        edges.pb({W[i], U[i], V[i]});
    }
    sort(edges.begin(), edges.end());
    dsu d(n);
    int id = 0;
    for(auto e : edges){
        d.join(e[1], e[2]);
    } 
}

int getMinimumFuelCapacity(int u, int v) {
    int nres;
    if(m == n - 1){
        nres = -1;
    }
    else{
        nres = edges.back()[0];
    }
    int ans = INF;
    int curr_time = 0;
    while(true){
        array<int, 2> tm = {curr_time, -1};
        auto it = lower_bound(merge_history[u].begin(), merge_history[u].end(), tm);
        auto it2 = lower_bound(merge_history[v].begin(), merge_history[v].end(), tm);
        int tf = INF;
        int ts = INF; 
        if(it != merge_history[u].end())
            tf = (*it)[0];
        if(it2 != merge_history[v].end())
            ts = (*it2)[0];
        if(tf == ts && tf == INF)
            break; 
        if(tf < ts){
            curr_time = tf + 1;
            u = (*it)[1];
        }
        else{
            curr_time = ts + 1;
            v = (*it2)[1];
        }
        if(u == v){
            if(good_history[u] != -1){
                ans = min(ans, max(edges[good_history[u]][0], edges[curr_time - 1][0]));
            }
        }
    }
    if(ans == INF){
        assert(nres == -1);
    }
    if(ans == INF)
        return -1;
    return ans; 
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:67:9: warning: unused variable 'id' [-Wunused-variable]
   67 |     int id = 0;
      |         ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 56 ms 8948 KB Output is correct
10 Correct 65 ms 10808 KB Output is correct
11 Correct 70 ms 10616 KB Output is correct
12 Correct 83 ms 11200 KB Output is correct
13 Correct 64 ms 11192 KB Output is correct
14 Correct 64 ms 9164 KB Output is correct
15 Correct 220 ms 13088 KB Output is correct
16 Correct 215 ms 12820 KB Output is correct
17 Correct 226 ms 13124 KB Output is correct
18 Correct 189 ms 13088 KB Output is correct
19 Runtime error 49 ms 8608 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 160 ms 14012 KB Output is correct
4 Correct 161 ms 13724 KB Output is correct
5 Correct 164 ms 14412 KB Output is correct
6 Correct 155 ms 13664 KB Output is correct
7 Correct 163 ms 13716 KB Output is correct
8 Correct 151 ms 14192 KB Output is correct
9 Correct 150 ms 13528 KB Output is correct
10 Correct 162 ms 13940 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 300 KB Output is correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 56 ms 8948 KB Output is correct
11 Correct 65 ms 10808 KB Output is correct
12 Correct 70 ms 10616 KB Output is correct
13 Correct 83 ms 11200 KB Output is correct
14 Correct 64 ms 11192 KB Output is correct
15 Correct 2 ms 324 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 300 KB Output is correct
20 Incorrect 1 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 56 ms 8948 KB Output is correct
10 Correct 65 ms 10808 KB Output is correct
11 Correct 70 ms 10616 KB Output is correct
12 Correct 83 ms 11200 KB Output is correct
13 Correct 64 ms 11192 KB Output is correct
14 Correct 64 ms 9164 KB Output is correct
15 Correct 220 ms 13088 KB Output is correct
16 Correct 215 ms 12820 KB Output is correct
17 Correct 226 ms 13124 KB Output is correct
18 Correct 189 ms 13088 KB Output is correct
19 Correct 160 ms 14012 KB Output is correct
20 Correct 161 ms 13724 KB Output is correct
21 Correct 164 ms 14412 KB Output is correct
22 Correct 155 ms 13664 KB Output is correct
23 Correct 163 ms 13716 KB Output is correct
24 Correct 151 ms 14192 KB Output is correct
25 Correct 150 ms 13528 KB Output is correct
26 Correct 162 ms 13940 KB Output is correct
27 Correct 2 ms 324 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 2 ms 300 KB Output is correct
32 Incorrect 1 ms 332 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 56 ms 8948 KB Output is correct
11 Correct 65 ms 10808 KB Output is correct
12 Correct 70 ms 10616 KB Output is correct
13 Correct 83 ms 11200 KB Output is correct
14 Correct 64 ms 11192 KB Output is correct
15 Correct 64 ms 9164 KB Output is correct
16 Correct 220 ms 13088 KB Output is correct
17 Correct 215 ms 12820 KB Output is correct
18 Correct 226 ms 13124 KB Output is correct
19 Correct 189 ms 13088 KB Output is correct
20 Correct 160 ms 14012 KB Output is correct
21 Correct 161 ms 13724 KB Output is correct
22 Correct 164 ms 14412 KB Output is correct
23 Correct 155 ms 13664 KB Output is correct
24 Correct 163 ms 13716 KB Output is correct
25 Correct 151 ms 14192 KB Output is correct
26 Correct 150 ms 13528 KB Output is correct
27 Correct 162 ms 13940 KB Output is correct
28 Correct 2 ms 324 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 2 ms 300 KB Output is correct
33 Incorrect 1 ms 332 KB Output isn't correct
34 Halted 0 ms 0 KB -