Submission #912415

#	Time	Username	Problem	Language	Result	Execution time	Memory
912415		Boycl07	Swapping Cities (APIO20_swap)	C++17	100 / 100	377 ms	62224 KiB

swap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task ""
#define sz(a) int(a.size())
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N_ = 1e5 + 4;
const int M_ = 2e5 + 4;
const int K_ = 1e5 + 4;
const int INF = 1e9;
const int LOG = 18;

int n, m;

int par[N_ + M_], f[N_ + M_], tin[N_ + M_], tout[N_ + M_];
array<int, 2> line[N_ + M_];
int weight[N_ + M_];
int up[N_ + M_][LOG + 1];
vector<int> g[N_ + M_];
int cur;

int find_set(int u) {
    return par[u] == u ? u : par[u] = find_set(par[u]);
}

void add_edge(int u, int v, int w)
{
    int x = find_set(u), y = find_set(v);
    ++cur;
    par[x] = par[y] = par[cur] = cur;
    f[cur] |= f[x] | f[y];
    g[cur].pb(x);
    weight[cur] = w;
    if(x != y)
    {
        g[cur].pb(y);
        line[cur] = line[x];
        bool flag = 0;
        forn(i, 0, 1)
            forn(j, 0, 1)
                if(min(u, v) == min(line[x][i], line[y][j]) && max(u, v) == max(line[x][i], line[y][j]))
                    {
                        line[cur] = {line[x][i ^ 1], line[y][j ^ 1]};
                        flag = 1;
                        break;
                    }
        if(!flag) f[cur] = 1;
    }
    else line[cur] = line[x], f[cur] = 1;
}

int timedfs = 0;

void dfs(int u, int p)
{
    tin[u] = ++timedfs;
    up[u][0] = p;
    forn(i, 1, LOG) up[u][i] = up[up[u][i - 1]][i - 1];
    for(int v : g[u]) dfs(v, u);
    tout[u] = timedfs;
}

void init(int n_, int m_, vector<int> U, vector<int> V, vector<int> W) {
    n = n_, m = m_;
    cur = n;
    vector<int> p;
    forn(i, 0, m - 1) p.pb(i);
    sort(all(p), [&W] (const int &x, const int &y) {
         return W[x] < W[y];
    });

    rep(i, n) par[i] = i, line[i] = {i, i};
    forn(i, 0, m - 1)
    {
        int u = U[p[i]] + 1, v = V[p[i]] + 1, w = W[p[i]];
        add_edge(u, v, w);
    }

    dfs(cur, cur);
}

bool is_anc(int u, int v)
{
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int getMinimumFuelCapacity(int u, int v) {
    ++u, ++v;
    ford(i, LOG, 0) if(!is_anc(up[u][i], v))
        u = up[u][i];
    if(!is_anc(u, v)) u = up[u][0];
    ford(i, LOG, 0) if(!f[up[u][i]]) u = up[u][i];
    if(!f[u]) u = up[u][0];
    if(!f[u]) return -1;
    return weight[u];
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27