oj.uz

답안 #319744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319744 2020-11-06T10:40:29 Z Everule 자매 도시 (APIO20_swap) C++17
0 / 100
 245 ms 13900 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;
        }
    } 
    return -1;
    if(mn == edges.size() + 1) return -1;
    return edges[mn-1].w;
}

Compilation message

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

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Correct 1 ms 404 KB Output is correct
4 Correct 1 ms 496 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 55 ms 9568 KB Output is correct
10 Correct 71 ms 11712 KB Output is correct
11 Correct 70 ms 11648 KB Output is correct
12 Correct 80 ms 12212 KB Output is correct
13 Correct 61 ms 11664 KB Output is correct
14 Correct 73 ms 9812 KB Output is correct
15 Correct 232 ms 13632 KB Output is correct
16 Correct 229 ms 13328 KB Output is correct
17 Correct 243 ms 13900 KB Output is correct
18 Correct 245 ms 13440 KB Output is correct
19 Incorrect 131 ms 4708 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Incorrect 224 ms 12896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Correct 1 ms 404 KB Output is correct
4 Correct 1 ms 496 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 55 ms 9568 KB Output is correct
10 Correct 71 ms 11712 KB Output is correct
11 Correct 70 ms 11648 KB Output is correct
12 Correct 80 ms 12212 KB Output is correct
13 Correct 61 ms 11664 KB Output is correct
14 Correct 73 ms 9812 KB Output is correct
15 Correct 232 ms 13632 KB Output is correct
16 Correct 229 ms 13328 KB Output is correct
17 Correct 243 ms 13900 KB Output is correct
18 Correct 245 ms 13440 KB Output is correct
19 Incorrect 224 ms 12896 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct