oj.uz

Submission #414211

# Submission time Handle Problem Language Result Execution time Memory
414211 2021-05-30T09:14:02 Z ACmachine Swapping Cities (APIO20_swap) C++17
7 / 100
 250 ms 17156 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 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)
        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 1 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 1 ms 296 KB Output is correct
5 Correct 1 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 50 ms 9912 KB Output is correct
10 Correct 61 ms 12012 KB Output is correct
11 Correct 62 ms 11876 KB Output is correct
12 Correct 89 ms 12564 KB Output is correct
13 Correct 83 ms 12620 KB Output is correct
14 Correct 64 ms 10264 KB Output is correct
15 Correct 250 ms 16244 KB Output is correct
16 Correct 213 ms 15976 KB Output is correct
17 Correct 216 ms 16448 KB Output is correct
18 Correct 150 ms 16404 KB Output is correct
19 Incorrect 97 ms 7156 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 175 ms 14888 KB Output is correct
4 Correct 146 ms 16420 KB Output is correct
5 Correct 177 ms 17156 KB Output is correct
6 Correct 149 ms 16296 KB Output is correct
7 Correct 158 ms 16504 KB Output is correct
8 Correct 146 ms 16780 KB Output is correct
9 Correct 200 ms 16272 KB Output is correct
10 Correct 148 ms 16628 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 296 KB Output is correct
5 Correct 1 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 1 ms 204 KB Output is correct
10 Correct 2 ms 300 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Incorrect 1 ms 316 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 50 ms 9912 KB Output is correct
11 Correct 61 ms 12012 KB Output is correct
12 Correct 62 ms 11876 KB Output is correct
13 Correct 89 ms 12564 KB Output is correct
14 Correct 83 ms 12620 KB Output is correct
15 Correct 2 ms 300 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Incorrect 1 ms 316 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 296 KB Output is correct
5 Correct 1 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 50 ms 9912 KB Output is correct
10 Correct 61 ms 12012 KB Output is correct
11 Correct 62 ms 11876 KB Output is correct
12 Correct 89 ms 12564 KB Output is correct
13 Correct 83 ms 12620 KB Output is correct
14 Correct 64 ms 10264 KB Output is correct
15 Correct 250 ms 16244 KB Output is correct
16 Correct 213 ms 15976 KB Output is correct
17 Correct 216 ms 16448 KB Output is correct
18 Correct 150 ms 16404 KB Output is correct
19 Correct 175 ms 14888 KB Output is correct
20 Correct 146 ms 16420 KB Output is correct
21 Correct 177 ms 17156 KB Output is correct
22 Correct 149 ms 16296 KB Output is correct
23 Correct 158 ms 16504 KB Output is correct
24 Correct 146 ms 16780 KB Output is correct
25 Correct 200 ms 16272 KB Output is correct
26 Correct 148 ms 16628 KB Output is correct
27 Correct 2 ms 300 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Incorrect 1 ms 316 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 50 ms 9912 KB Output is correct
11 Correct 61 ms 12012 KB Output is correct
12 Correct 62 ms 11876 KB Output is correct
13 Correct 89 ms 12564 KB Output is correct
14 Correct 83 ms 12620 KB Output is correct
15 Correct 64 ms 10264 KB Output is correct
16 Correct 250 ms 16244 KB Output is correct
17 Correct 213 ms 15976 KB Output is correct
18 Correct 216 ms 16448 KB Output is correct
19 Correct 150 ms 16404 KB Output is correct
20 Correct 175 ms 14888 KB Output is correct
21 Correct 146 ms 16420 KB Output is correct
22 Correct 177 ms 17156 KB Output is correct
23 Correct 149 ms 16296 KB Output is correct
24 Correct 158 ms 16504 KB Output is correct
25 Correct 146 ms 16780 KB Output is correct
26 Correct 200 ms 16272 KB Output is correct
27 Correct 148 ms 16628 KB Output is correct
28 Correct 2 ms 300 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Incorrect 1 ms 316 KB Output isn't correct
34 Halted 0 ms 0 KB -