oj.uz

Submission #502389

# Submission time Handle Problem Language Result Execution time Memory
502389 2022-01-05T21:03:59 Z Victor Swapping Cities (APIO20_swap) C++17
24 / 100
 2000 ms 26336 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

struct ufds_rollback {
    vector<map<int,int>>p;
    vi rank,max_deg,possible,deg;
    vector<bool>cycle;
    
    ufds_rollback(int n) {
        deg.assign(n,0);
        rank.assign(n,0);
        cycle.assign(n,0);
        max_deg.assign(n,0);
        possible.assign(n,INF);

        p.resize(n);
        rep(i,0,n)p[i].emplace(0,i);
    }

    int find(int i,const int &mx) {
        auto it=p[i].upper_bound(mx);
        --it;
        //cout<<"i = "<<i<<" mx = "<<mx<<" val = "<<it->first<<" p = "<<it->second<<endl;
        if(it->second==i)return i;
        else return find(it->second,mx);
        return 0;
    }

    void union_set(int i,int j,int val) {
        int u=find(i,val);
        int v=find(j,val);
        if(u==v) {
            cycle[u]=1;
            possible[u]=min(possible[u],val);
            return;
        }

        ++deg[i];
        ++deg[j];
        max_deg[u]=max(max_deg[u],deg[i]);
        max_deg[v]=max(max_deg[v],deg[j]);

        if(rank[u]<rank[v])swap(u,v);
        p[v][val]=u;
        max_deg[u]=max(max_deg[u],max_deg[v]);
        
        if(possible[v]!=INF||max_deg[u]>=3) possible[u]=min(possible[u],val);
    }
};

ufds_rollback ufds(100001);
vector<iii> edges;
int n,m;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N;
    m=M;
    rep(i,0,m) edges.pb({W[i],{U[i],V[i]}});
    sort(all(edges));
    //rep(i,0,n) {
    //    auto it=ufds.p[i].begin();
    //    cout<<sz(ufds.p[i])<<' '<<it->first<<' '<<it->second<<' ';
    //    ufds.find(i,0);
    //}
    trav(edge,edges) {
        int u,v,w;
        w=edge.first;
        tie(u,v)=edge.second;
        ufds.union_set(u,v,w);
        //cout<<"u = "<<u<<" v = "<<v<<" w = "<<w<<endl;
    }
    edges.pb({-1,{0,0}});
}

int getMinimumFuelCapacity(int X, int Y) {
    int u=X,v=Y;
    int lo=0,hi=m;
    while(lo!=hi) {
        int mid=(lo+hi)/2;
        int w=edges[mid].first;
        int p=ufds.find(u,w);
        if(p==ufds.find(v,w)&&ufds.possible[p]<=w) hi=mid;
        else lo=mid+1;
    }
    return edges[lo].first;
}

/*
int main() {
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));

    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
        assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
    }

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        assert(2 == scanf("%d %d", &X[i], &Y[i]));
    }

    init(N, M, U, V, W);

    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }

    for (int i = 0; i < Q; ++i) {
        printf("%d\n", minimum_fuel_capacities[i]);
    }

    return 0;
}*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11212 KB Output is correct
2 Correct 12 ms 11184 KB Output is correct
3 Correct 8 ms 11284 KB Output is correct
4 Correct 9 ms 11212 KB Output is correct
5 Correct 9 ms 11296 KB Output is correct
6 Correct 9 ms 11288 KB Output is correct
7 Correct 9 ms 11292 KB Output is correct
8 Correct 9 ms 11340 KB Output is correct
9 Correct 63 ms 19316 KB Output is correct
10 Correct 79 ms 21176 KB Output is correct
11 Correct 77 ms 20920 KB Output is correct
12 Correct 82 ms 21548 KB Output is correct
13 Correct 156 ms 21560 KB Output is correct
14 Correct 112 ms 19784 KB Output is correct
15 Correct 626 ms 25272 KB Output is correct
16 Correct 643 ms 25140 KB Output is correct
17 Correct 660 ms 25680 KB Output is correct
18 Execution timed out 2061 ms 25400 KB Time limit exceeded

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11212 KB Output is correct
2 Correct 12 ms 11184 KB Output is correct
3 Correct 235 ms 25788 KB Output is correct
4 Correct 233 ms 26144 KB Output is correct
5 Correct 247 ms 26252 KB Output is correct
6 Correct 236 ms 26272 KB Output is correct
7 Correct 243 ms 26336 KB Output is correct
8 Correct 241 ms 25904 KB Output is correct
9 Correct 237 ms 26028 KB Output is correct
10 Correct 248 ms 25824 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11212 KB Output is correct
2 Correct 12 ms 11184 KB Output is correct
3 Correct 8 ms 11284 KB Output is correct
4 Correct 9 ms 11212 KB Output is correct
5 Correct 9 ms 11296 KB Output is correct
6 Correct 9 ms 11288 KB Output is correct
7 Correct 9 ms 11292 KB Output is correct
8 Correct 9 ms 11340 KB Output is correct
9 Correct 8 ms 11228 KB Output is correct
10 Correct 9 ms 11284 KB Output is correct
11 Correct 9 ms 11296 KB Output is correct
12 Correct 10 ms 11296 KB Output is correct
13 Correct 9 ms 11328 KB Output is correct
14 Correct 9 ms 11340 KB Output is correct
15 Correct 9 ms 11340 KB Output is correct
16 Correct 9 ms 11340 KB Output is correct
17 Correct 9 ms 11276 KB Output is correct
18 Correct 9 ms 11256 KB Output is correct
19 Correct 9 ms 11288 KB Output is correct
20 Correct 8 ms 11300 KB Output is correct
21 Correct 9 ms 11308 KB Output is correct
22 Correct 9 ms 11340 KB Output is correct
23 Correct 9 ms 11340 KB Output is correct
24 Correct 9 ms 11392 KB Output is correct
25 Correct 9 ms 11420 KB Output is correct
26 Correct 9 ms 11340 KB Output is correct
27 Correct 9 ms 11340 KB Output is correct
28 Correct 11 ms 11340 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11228 KB Output is correct
2 Correct 9 ms 11212 KB Output is correct
3 Correct 12 ms 11184 KB Output is correct
4 Correct 8 ms 11284 KB Output is correct
5 Correct 9 ms 11212 KB Output is correct
6 Correct 9 ms 11296 KB Output is correct
7 Correct 9 ms 11288 KB Output is correct
8 Correct 9 ms 11292 KB Output is correct
9 Correct 9 ms 11340 KB Output is correct
10 Correct 63 ms 19316 KB Output is correct
11 Correct 79 ms 21176 KB Output is correct
12 Correct 77 ms 20920 KB Output is correct
13 Correct 82 ms 21548 KB Output is correct
14 Correct 156 ms 21560 KB Output is correct
15 Correct 9 ms 11284 KB Output is correct
16 Correct 9 ms 11296 KB Output is correct
17 Correct 10 ms 11296 KB Output is correct
18 Correct 9 ms 11328 KB Output is correct
19 Correct 9 ms 11340 KB Output is correct
20 Correct 9 ms 11340 KB Output is correct
21 Correct 9 ms 11340 KB Output is correct
22 Correct 9 ms 11276 KB Output is correct
23 Correct 9 ms 11256 KB Output is correct
24 Correct 9 ms 11288 KB Output is correct
25 Correct 8 ms 11300 KB Output is correct
26 Correct 9 ms 11308 KB Output is correct
27 Correct 9 ms 11340 KB Output is correct
28 Correct 9 ms 11340 KB Output is correct
29 Correct 9 ms 11392 KB Output is correct
30 Correct 9 ms 11420 KB Output is correct
31 Correct 9 ms 11340 KB Output is correct
32 Correct 9 ms 11340 KB Output is correct
33 Correct 11 ms 11340 KB Output is correct
34 Correct 16 ms 12628 KB Output is correct
35 Correct 80 ms 21396 KB Output is correct
36 Correct 79 ms 21240 KB Output is correct
37 Correct 85 ms 21236 KB Output is correct
38 Correct 80 ms 21104 KB Output is correct
39 Correct 83 ms 21084 KB Output is correct
40 Correct 76 ms 20232 KB Output is correct
41 Correct 84 ms 21512 KB Output is correct
42 Correct 83 ms 21224 KB Output is correct
43 Correct 105 ms 21236 KB Output is correct
44 Correct 100 ms 21504 KB Output is correct
45 Execution timed out 2016 ms 22740 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11212 KB Output is correct
2 Correct 12 ms 11184 KB Output is correct
3 Correct 8 ms 11284 KB Output is correct
4 Correct 9 ms 11212 KB Output is correct
5 Correct 9 ms 11296 KB Output is correct
6 Correct 9 ms 11288 KB Output is correct
7 Correct 9 ms 11292 KB Output is correct
8 Correct 9 ms 11340 KB Output is correct
9 Correct 63 ms 19316 KB Output is correct
10 Correct 79 ms 21176 KB Output is correct
11 Correct 77 ms 20920 KB Output is correct
12 Correct 82 ms 21548 KB Output is correct
13 Correct 156 ms 21560 KB Output is correct
14 Correct 112 ms 19784 KB Output is correct
15 Correct 626 ms 25272 KB Output is correct
16 Correct 643 ms 25140 KB Output is correct
17 Correct 660 ms 25680 KB Output is correct
18 Execution timed out 2061 ms 25400 KB Time limit exceeded

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11228 KB Output is correct
2 Correct 9 ms 11212 KB Output is correct
3 Correct 12 ms 11184 KB Output is correct
4 Correct 8 ms 11284 KB Output is correct
5 Correct 9 ms 11212 KB Output is correct
6 Correct 9 ms 11296 KB Output is correct
7 Correct 9 ms 11288 KB Output is correct
8 Correct 9 ms 11292 KB Output is correct
9 Correct 9 ms 11340 KB Output is correct
10 Correct 63 ms 19316 KB Output is correct
11 Correct 79 ms 21176 KB Output is correct
12 Correct 77 ms 20920 KB Output is correct
13 Correct 82 ms 21548 KB Output is correct
14 Correct 156 ms 21560 KB Output is correct
15 Correct 112 ms 19784 KB Output is correct
16 Correct 626 ms 25272 KB Output is correct
17 Correct 643 ms 25140 KB Output is correct
18 Correct 660 ms 25680 KB Output is correct
19 Execution timed out 2061 ms 25400 KB Time limit exceeded