oj.uz

Submission #912407

# Submission time Handle Problem Language Result Execution time Memory
912407 2024-01-19T12:07:44 Z Boycl07 Swapping Cities (APIO20_swap) C++17
6 / 100
 277 ms 46832 KB 
#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];
    u = up[u][0];
    if(!f[u]) return -1;
    return weight[u];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16984 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 5 ms 17028 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 80 ms 35532 KB Output is correct
10 Correct 112 ms 38860 KB Output is correct
11 Correct 113 ms 38880 KB Output is correct
12 Correct 118 ms 39284 KB Output is correct
13 Correct 89 ms 41680 KB Output is correct
14 Correct 104 ms 35792 KB Output is correct
15 Correct 204 ms 42956 KB Output is correct
16 Correct 202 ms 42700 KB Output is correct
17 Correct 240 ms 43468 KB Output is correct
18 Correct 222 ms 45432 KB Output is correct
19 Correct 88 ms 25396 KB Output is correct
20 Correct 214 ms 44104 KB Output is correct
21 Correct 222 ms 43888 KB Output is correct
22 Correct 268 ms 44400 KB Output is correct
23 Correct 223 ms 46832 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16984 KB Output is correct
3 Incorrect 277 ms 44020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 4 ms 16984 KB Output is correct
5 Correct 5 ms 16988 KB Output is correct
6 Correct 5 ms 17028 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 80 ms 35532 KB Output is correct
11 Correct 112 ms 38860 KB Output is correct
12 Correct 113 ms 38880 KB Output is correct
13 Correct 118 ms 39284 KB Output is correct
14 Correct 89 ms 41680 KB Output is correct
15 Incorrect 4 ms 16988 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16984 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 5 ms 17028 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 80 ms 35532 KB Output is correct
10 Correct 112 ms 38860 KB Output is correct
11 Correct 113 ms 38880 KB Output is correct
12 Correct 118 ms 39284 KB Output is correct
13 Correct 89 ms 41680 KB Output is correct
14 Correct 104 ms 35792 KB Output is correct
15 Correct 204 ms 42956 KB Output is correct
16 Correct 202 ms 42700 KB Output is correct
17 Correct 240 ms 43468 KB Output is correct
18 Correct 222 ms 45432 KB Output is correct
19 Incorrect 277 ms 44020 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 4 ms 16984 KB Output is correct
5 Correct 5 ms 16988 KB Output is correct
6 Correct 5 ms 17028 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 80 ms 35532 KB Output is correct
11 Correct 112 ms 38860 KB Output is correct
12 Correct 113 ms 38880 KB Output is correct
13 Correct 118 ms 39284 KB Output is correct
14 Correct 89 ms 41680 KB Output is correct
15 Correct 104 ms 35792 KB Output is correct
16 Correct 204 ms 42956 KB Output is correct
17 Correct 202 ms 42700 KB Output is correct
18 Correct 240 ms 43468 KB Output is correct
19 Correct 222 ms 45432 KB Output is correct
20 Incorrect 277 ms 44020 KB Output isn't correct
21 Halted 0 ms 0 KB -