oj.uz

Submission #319740

# Submission time Handle Problem Language Result Execution time Memory
319740 2020-11-06T10:30:37 Z Everule Swapping Cities (APIO20_swap) C++17
6 / 100
 263 ms 19532 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out<<x<<" ";
    }
    out<<"\n";
    return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out+x;
    }
    return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
    for(auto &x : vec){
        in>>x;
    }
    return in;
}
struct Persistent_DSU{
    int n;
    vector<int> par;
    vector<int> partime;
    struct state{
        int edges, size, time;
        state(int edges, int size,int time) : edges(edges), size(size), time(time) {}
        state() {}
        bool operator<(const state &o){
            return time<o.time;
        }
        bool operator<(int t){
            return time < t;
        }
    };
    vector<vector<state>> sz;
    int currtime = 0;
    Persistent_DSU(int n) : n(n){
        par.resize(n);
        iota(par.begin(), par.end(), 0);
        partime.assign(n, -1);
        sz.assign(n, {state(0,1,0)});
    }
    int find_set(int u,int t){
        while(par[u] != u && partime[u] < t){
            u = par[u];
        }
        return u;
    }
    void join_sets(int u,int v){
        int r1 = find_set(u, currtime);
        int r2 = find_set(v, currtime);
        if(r1 == r2){
            auto s = sz[r1].back();
            s.edges++;
            s.time = currtime;
            sz[r1].push_back(s);
            ++currtime;
            return;
        }
        auto [e1,s1,t1] = sz[r1].back();
        auto [e2,s2,t2] = sz[r2].back();
        if(s1 > s2){
            swap(r1,r2);
        }
        par[r1] = r2;
        partime[r1] = currtime;
        sz[r2].push_back(state(e1+e2+1,s1+s2,currtime));
        ++currtime;
    }
    state findstate(int u,int t){
        auto it = lower_bound(sz[u].begin(), sz[u].end(), t);
        --it;
        return (*it);
    }
};
struct Edge{
    int u,v,w;
    Edge(int u,int v,int w) : u(u), v(v), w(w) {}
    Edge() {}
    bool operator<(const Edge &o){
        return w < o.w;
    }
};
Persistent_DSU dsu(0);
vector<Edge> edges;
void init(int n,int m, vector<int> u, vector<int> v, vector<int> w){
    edges.resize(m);
    dsu = Persistent_DSU(n);
    for(int i=0;i<m;i++){
        edges[i] = Edge(u[i],v[i],w[i]);
    }
    sort(edges.begin(), edges.end());
    for(const auto &[u,v,w] : edges){
        dsu.join_sets(u,v);
    }
}
int getMinimumFuelCapacity(int x,int y){
    int mn = 1, mx = edges.size() + 1;
    while(mn < mx){
        int mid = mn + mx;
        mid>>=1;
        int r1 = dsu.find_set(x, mid);
        int r2 = dsu.find_set(y, mid);
        if(r1 != r2){
            mn = mid + 1;
            continue;
        }
        auto s = dsu.findstate(r1, mid);
        if(s.edges < s.size){
            mn = mid + 1;
        }
        else{
            mx = mid;
        }
    } 
    if(mn == edges.size() + 1) return -1;
    return edges[mn-1].w;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:124:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     if(mn == edges.size() + 1) return -1;
      |        ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 57 ms 9572 KB Output is correct
10 Correct 72 ms 11620 KB Output is correct
11 Correct 68 ms 11524 KB Output is correct
12 Correct 76 ms 12132 KB Output is correct
13 Correct 59 ms 11792 KB Output is correct
14 Correct 73 ms 9700 KB Output is correct
15 Correct 237 ms 13552 KB Output is correct
16 Correct 234 ms 13204 KB Output is correct
17 Correct 244 ms 13900 KB Output is correct
18 Correct 203 ms 13456 KB Output is correct
19 Correct 129 ms 5764 KB Output is correct
20 Correct 233 ms 18916 KB Output is correct
21 Correct 239 ms 18848 KB Output is correct
22 Correct 263 ms 19532 KB Output is correct
23 Correct 212 ms 19064 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 215 ms 12768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 1 ms 492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 57 ms 9572 KB Output is correct
11 Correct 72 ms 11620 KB Output is correct
12 Correct 68 ms 11524 KB Output is correct
13 Correct 76 ms 12132 KB Output is correct
14 Correct 59 ms 11792 KB Output is correct
15 Incorrect 1 ms 492 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 57 ms 9572 KB Output is correct
10 Correct 72 ms 11620 KB Output is correct
11 Correct 68 ms 11524 KB Output is correct
12 Correct 76 ms 12132 KB Output is correct
13 Correct 59 ms 11792 KB Output is correct
14 Correct 73 ms 9700 KB Output is correct
15 Correct 237 ms 13552 KB Output is correct
16 Correct 234 ms 13204 KB Output is correct
17 Correct 244 ms 13900 KB Output is correct
18 Correct 203 ms 13456 KB Output is correct
19 Incorrect 215 ms 12768 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 57 ms 9572 KB Output is correct
11 Correct 72 ms 11620 KB Output is correct
12 Correct 68 ms 11524 KB Output is correct
13 Correct 76 ms 12132 KB Output is correct
14 Correct 59 ms 11792 KB Output is correct
15 Correct 73 ms 9700 KB Output is correct
16 Correct 237 ms 13552 KB Output is correct
17 Correct 234 ms 13204 KB Output is correct
18 Correct 244 ms 13900 KB Output is correct
19 Correct 203 ms 13456 KB Output is correct
20 Incorrect 215 ms 12768 KB Output isn't correct
21 Halted 0 ms 0 KB -