Submission #319735

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
319735	2020-11-06T10:22:08 Z	Everule	Swapping Cities (APIO20_swap)	C++17	Compilation error	0 ms	0 KB

swap

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;
vector<Edge> edges;
int init(int n,int m, int u[], int v[], int w[]){
    edges.resize(m);
    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;
    else return edges[mn-1].w;
}

Compilation message

swap.cpp:3:5: error: 'vector' does not name a type
    3 |     vector<int> par;
      |     ^~~~~~
swap.cpp:4:5: error: 'vector' does not name a type
    4 |     vector<int> partime;
      |     ^~~~~~
swap.cpp:16:5: error: 'vector' does not name a type
   16 |     vector<vector<state>> sz;
      |     ^~~~~~
swap.cpp: In constructor 'Persistent_DSU::Persistent_DSU(int)':
swap.cpp:19:9: error: 'par' was not declared in this scope
   19 |         par.resize(n);
      |         ^~~
swap.cpp:20:9: error: 'iota' was not declared in this scope
   20 |         iota(par.begin(), par.end(), 0);
      |         ^~~~
swap.cpp:21:9: error: 'partime' was not declared in this scope
   21 |         partime.assign(n, -1);
      |         ^~~~~~~
swap.cpp:22:9: error: 'sz' was not declared in this scope
   22 |         sz.assign(n, {state(0,1,0)});
      |         ^~
swap.cpp: In member function 'int Persistent_DSU::find_set(int, int)':
swap.cpp:25:15: error: 'par' was not declared in this scope
   25 |         while(par[u] != u && partime[u] < t){
      |               ^~~
swap.cpp:25:30: error: 'partime' was not declared in this scope
   25 |         while(par[u] != u && partime[u] < t){
      |                              ^~~~~~~
swap.cpp: In member function 'void Persistent_DSU::join_sets(int, int)':
swap.cpp:34:22: error: 'sz' was not declared in this scope; did you mean 's'?
   34 |             auto s = sz[r1].back();
      |                      ^~
      |                      s
swap.cpp:41:27: error: 'sz' was not declared in this scope; did you mean 's1'?
   41 |         auto [e1,s1,t1] = sz[r1].back();
      |                           ^~
      |                           s1
swap.cpp:44:13: error: 'swap' was not declared in this scope
   44 |             swap(r1,r2);
      |             ^~~~
swap.cpp:46:9: error: 'par' was not declared in this scope
   46 |         par[r1] = r2;
      |         ^~~
swap.cpp:47:9: error: 'partime' was not declared in this scope
   47 |         partime[r1] = currtime;
      |         ^~~~~~~
swap.cpp: In member function 'Persistent_DSU::state Persistent_DSU::findstate(int, int)':
swap.cpp:52:31: error: 'sz' was not declared in this scope
   52 |         auto it = lower_bound(sz[u].begin(), sz[u].end(), t);
      |                               ^~
swap.cpp:52:19: error: 'lower_bound' was not declared in this scope
   52 |         auto it = lower_bound(sz[u].begin(), sz[u].end(), t);
      |                   ^~~~~~~~~~~
swap.cpp: At global scope:
swap.cpp:66:16: error: no matching function for call to 'Persistent_DSU::Persistent_DSU()'
   66 | Persistent_DSU dsu;
      |                ^~~
swap.cpp:18:5: note: candidate: 'Persistent_DSU::Persistent_DSU(int)'
   18 |     Persistent_DSU(int n) : n(n){
      |     ^~~~~~~~~~~~~~
swap.cpp:18:5: note:   candidate expects 1 argument, 0 provided
swap.cpp:1:8: note: candidate: 'constexpr Persistent_DSU::Persistent_DSU(const Persistent_DSU&)'
    1 | struct Persistent_DSU{
      |        ^~~~~~~~~~~~~~
swap.cpp:1:8: note:   candidate expects 1 argument, 0 provided
swap.cpp:1:8: note: candidate: 'constexpr Persistent_DSU::Persistent_DSU(Persistent_DSU&&)'
swap.cpp:1:8: note:   candidate expects 1 argument, 0 provided
swap.cpp:67:1: error: 'vector' does not name a type
   67 | vector<Edge> edges;
      | ^~~~~~
swap.cpp: In function 'int init(int, int, int*, int*, int*)':
swap.cpp:69:5: error: 'edges' was not declared in this scope
   69 |     edges.resize(m);
      |     ^~~~~
swap.cpp:74:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   74 |     sort(edges.begin(), edges.end());
      |     ^~~~
      |     short
swap.cpp:78:1: warning: no return statement in function returning non-void [-Wreturn-type]
   78 | }
      | ^
swap.cpp: In function 'int getminimumFuelCapacity(int, int)':
swap.cpp:80:22: error: 'edges' was not declared in this scope
   80 |     int mn = 1, mx = edges.size() + 1;
      |                      ^~~~~