oj.uz

Submission #319739

# Submission time Handle Problem Language Result Execution time Memory
319739 2020-11-06T10:25:59 Z Everule Swapping Cities (APIO20_swap) C++17
0 / 100
 152 ms 24164 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);
    }
};
const int INF = 1e9;
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]);
    }
    Persistent_DSU dsu(n);
    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:126:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     if(mn == edges.size() + 1) return -1;
      |        ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
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 512 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 63 ms 16228 KB Output is correct
10 Correct 78 ms 19884 KB Output is correct
11 Correct 76 ms 19424 KB Output is correct
12 Correct 82 ms 20580 KB Output is correct
13 Correct 70 ms 19992 KB Output is correct
14 Correct 71 ms 16484 KB Output is correct
15 Correct 151 ms 23652 KB Output is correct
16 Correct 150 ms 23140 KB Output is correct
17 Correct 152 ms 24164 KB Output is correct
18 Correct 145 ms 23712 KB Output is correct
19 Incorrect 67 ms 7280 KB Output isn't correct
20 Halted 0 ms 0 KB -

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 133 ms 22496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

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 512 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 63 ms 16228 KB Output is correct
10 Correct 78 ms 19884 KB Output is correct
11 Correct 76 ms 19424 KB Output is correct
12 Correct 82 ms 20580 KB Output is correct
13 Correct 70 ms 19992 KB Output is correct
14 Correct 71 ms 16484 KB Output is correct
15 Correct 151 ms 23652 KB Output is correct
16 Correct 150 ms 23140 KB Output is correct
17 Correct 152 ms 24164 KB Output is correct
18 Correct 145 ms 23712 KB Output is correct
19 Incorrect 133 ms 22496 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct