oj.uz

Submission #912415

# Submission time Handle Problem Language Result Execution time Memory
912415 2024-01-19T12:22:03 Z Boycl07 Swapping Cities (APIO20_swap) C++17
100 / 100
 377 ms 62224 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];
    if(!f[u]) 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 17032 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 17048 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 5 ms 16984 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 101 ms 33844 KB Output is correct
10 Correct 108 ms 37064 KB Output is correct
11 Correct 112 ms 36944 KB Output is correct
12 Correct 132 ms 37324 KB Output is correct
13 Correct 99 ms 39860 KB Output is correct
14 Correct 97 ms 34248 KB Output is correct
15 Correct 231 ms 38604 KB Output is correct
16 Correct 209 ms 38476 KB Output is correct
17 Correct 216 ms 38956 KB Output is correct
18 Correct 229 ms 41164 KB Output is correct
19 Correct 91 ms 23412 KB Output is correct
20 Correct 231 ms 39660 KB Output is correct
21 Correct 205 ms 39552 KB Output is correct
22 Correct 214 ms 40056 KB Output is correct
23 Correct 224 ms 42660 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 17032 KB Output is correct
3 Correct 211 ms 43900 KB Output is correct
4 Correct 268 ms 48264 KB Output is correct
5 Correct 225 ms 48232 KB Output is correct
6 Correct 211 ms 48084 KB Output is correct
7 Correct 220 ms 48328 KB Output is correct
8 Correct 225 ms 47760 KB Output is correct
9 Correct 242 ms 47972 KB Output is correct
10 Correct 264 ms 47920 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 17032 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 17048 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 5 ms 16984 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 4 ms 16996 KB Output is correct
12 Correct 5 ms 16988 KB Output is correct
13 Correct 5 ms 16988 KB Output is correct
14 Correct 5 ms 16988 KB Output is correct
15 Correct 5 ms 16988 KB Output is correct
16 Correct 5 ms 16984 KB Output is correct
17 Correct 6 ms 17028 KB Output is correct
18 Correct 6 ms 16984 KB Output is correct
19 Correct 5 ms 16988 KB Output is correct
20 Correct 4 ms 16988 KB Output is correct
21 Correct 5 ms 16988 KB Output is correct
22 Correct 5 ms 17104 KB Output is correct
23 Correct 5 ms 16988 KB Output is correct
24 Correct 5 ms 17200 KB Output is correct
25 Correct 5 ms 16988 KB Output is correct
26 Correct 6 ms 17240 KB Output is correct
27 Correct 5 ms 16988 KB Output is correct
28 Correct 6 ms 16988 KB Output is correct

Subtask #4
20.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 17032 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 17048 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 16984 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 101 ms 33844 KB Output is correct
11 Correct 108 ms 37064 KB Output is correct
12 Correct 112 ms 36944 KB Output is correct
13 Correct 132 ms 37324 KB Output is correct
14 Correct 99 ms 39860 KB Output is correct
15 Correct 4 ms 16988 KB Output is correct
16 Correct 4 ms 16996 KB Output is correct
17 Correct 5 ms 16988 KB Output is correct
18 Correct 5 ms 16988 KB Output is correct
19 Correct 5 ms 16988 KB Output is correct
20 Correct 5 ms 16988 KB Output is correct
21 Correct 5 ms 16984 KB Output is correct
22 Correct 6 ms 17028 KB Output is correct
23 Correct 6 ms 16984 KB Output is correct
24 Correct 5 ms 16988 KB Output is correct
25 Correct 4 ms 16988 KB Output is correct
26 Correct 5 ms 16988 KB Output is correct
27 Correct 5 ms 17104 KB Output is correct
28 Correct 5 ms 16988 KB Output is correct
29 Correct 5 ms 17200 KB Output is correct
30 Correct 5 ms 16988 KB Output is correct
31 Correct 6 ms 17240 KB Output is correct
32 Correct 5 ms 16988 KB Output is correct
33 Correct 6 ms 16988 KB Output is correct
34 Correct 15 ms 20060 KB Output is correct
35 Correct 134 ms 39124 KB Output is correct
36 Correct 118 ms 39116 KB Output is correct
37 Correct 121 ms 39120 KB Output is correct
38 Correct 113 ms 38820 KB Output is correct
39 Correct 145 ms 38756 KB Output is correct
40 Correct 115 ms 36296 KB Output is correct
41 Correct 132 ms 39368 KB Output is correct
42 Correct 117 ms 39116 KB Output is correct
43 Correct 95 ms 42140 KB Output is correct
44 Correct 134 ms 39372 KB Output is correct
45 Correct 133 ms 49540 KB Output is correct
46 Correct 120 ms 39116 KB Output is correct
47 Correct 126 ms 39372 KB Output is correct
48 Correct 128 ms 41676 KB Output is correct
49 Correct 92 ms 48584 KB Output is correct
50 Correct 72 ms 39908 KB Output is correct
51 Correct 122 ms 45584 KB Output is correct
52 Correct 154 ms 51528 KB Output is correct
53 Correct 184 ms 54856 KB Output is correct
54 Correct 185 ms 58312 KB Output is correct
55 Correct 96 ms 41932 KB Output is correct
56 Correct 170 ms 56212 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 17032 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 17048 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 5 ms 16984 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 101 ms 33844 KB Output is correct
10 Correct 108 ms 37064 KB Output is correct
11 Correct 112 ms 36944 KB Output is correct
12 Correct 132 ms 37324 KB Output is correct
13 Correct 99 ms 39860 KB Output is correct
14 Correct 97 ms 34248 KB Output is correct
15 Correct 231 ms 38604 KB Output is correct
16 Correct 209 ms 38476 KB Output is correct
17 Correct 216 ms 38956 KB Output is correct
18 Correct 229 ms 41164 KB Output is correct
19 Correct 211 ms 43900 KB Output is correct
20 Correct 268 ms 48264 KB Output is correct
21 Correct 225 ms 48232 KB Output is correct
22 Correct 211 ms 48084 KB Output is correct
23 Correct 220 ms 48328 KB Output is correct
24 Correct 225 ms 47760 KB Output is correct
25 Correct 242 ms 47972 KB Output is correct
26 Correct 264 ms 47920 KB Output is correct
27 Correct 4 ms 16988 KB Output is correct
28 Correct 4 ms 16996 KB Output is correct
29 Correct 5 ms 16988 KB Output is correct
30 Correct 5 ms 16988 KB Output is correct
31 Correct 5 ms 16988 KB Output is correct
32 Correct 5 ms 16988 KB Output is correct
33 Correct 5 ms 16984 KB Output is correct
34 Correct 6 ms 17028 KB Output is correct
35 Correct 6 ms 16984 KB Output is correct
36 Correct 15 ms 20060 KB Output is correct
37 Correct 134 ms 39124 KB Output is correct
38 Correct 118 ms 39116 KB Output is correct
39 Correct 121 ms 39120 KB Output is correct
40 Correct 113 ms 38820 KB Output is correct
41 Correct 145 ms 38756 KB Output is correct
42 Correct 115 ms 36296 KB Output is correct
43 Correct 132 ms 39368 KB Output is correct
44 Correct 117 ms 39116 KB Output is correct
45 Correct 95 ms 42140 KB Output is correct
46 Correct 134 ms 39372 KB Output is correct
47 Correct 23 ms 20572 KB Output is correct
48 Correct 209 ms 43592 KB Output is correct
49 Correct 214 ms 43536 KB Output is correct
50 Correct 211 ms 43432 KB Output is correct
51 Correct 211 ms 43484 KB Output is correct
52 Correct 194 ms 43116 KB Output is correct
53 Correct 174 ms 38008 KB Output is correct
54 Correct 221 ms 44456 KB Output is correct
55 Correct 238 ms 43612 KB Output is correct
56 Correct 262 ms 45952 KB Output is correct
57 Correct 248 ms 44400 KB Output is correct

Subtask #6
27.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 17032 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 17048 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 16984 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 101 ms 33844 KB Output is correct
11 Correct 108 ms 37064 KB Output is correct
12 Correct 112 ms 36944 KB Output is correct
13 Correct 132 ms 37324 KB Output is correct
14 Correct 99 ms 39860 KB Output is correct
15 Correct 97 ms 34248 KB Output is correct
16 Correct 231 ms 38604 KB Output is correct
17 Correct 209 ms 38476 KB Output is correct
18 Correct 216 ms 38956 KB Output is correct
19 Correct 229 ms 41164 KB Output is correct
20 Correct 211 ms 43900 KB Output is correct
21 Correct 268 ms 48264 KB Output is correct
22 Correct 225 ms 48232 KB Output is correct
23 Correct 211 ms 48084 KB Output is correct
24 Correct 220 ms 48328 KB Output is correct
25 Correct 225 ms 47760 KB Output is correct
26 Correct 242 ms 47972 KB Output is correct
27 Correct 264 ms 47920 KB Output is correct
28 Correct 4 ms 16988 KB Output is correct
29 Correct 4 ms 16996 KB Output is correct
30 Correct 5 ms 16988 KB Output is correct
31 Correct 5 ms 16988 KB Output is correct
32 Correct 5 ms 16988 KB Output is correct
33 Correct 5 ms 16988 KB Output is correct
34 Correct 5 ms 16984 KB Output is correct
35 Correct 6 ms 17028 KB Output is correct
36 Correct 6 ms 16984 KB Output is correct
37 Correct 15 ms 20060 KB Output is correct
38 Correct 134 ms 39124 KB Output is correct
39 Correct 118 ms 39116 KB Output is correct
40 Correct 121 ms 39120 KB Output is correct
41 Correct 113 ms 38820 KB Output is correct
42 Correct 145 ms 38756 KB Output is correct
43 Correct 115 ms 36296 KB Output is correct
44 Correct 132 ms 39368 KB Output is correct
45 Correct 117 ms 39116 KB Output is correct
46 Correct 95 ms 42140 KB Output is correct
47 Correct 134 ms 39372 KB Output is correct
48 Correct 23 ms 20572 KB Output is correct
49 Correct 209 ms 43592 KB Output is correct
50 Correct 214 ms 43536 KB Output is correct
51 Correct 211 ms 43432 KB Output is correct
52 Correct 211 ms 43484 KB Output is correct
53 Correct 194 ms 43116 KB Output is correct
54 Correct 174 ms 38008 KB Output is correct
55 Correct 221 ms 44456 KB Output is correct
56 Correct 238 ms 43612 KB Output is correct
57 Correct 262 ms 45952 KB Output is correct
58 Correct 248 ms 44400 KB Output is correct
59 Correct 91 ms 23412 KB Output is correct
60 Correct 231 ms 39660 KB Output is correct
61 Correct 205 ms 39552 KB Output is correct
62 Correct 214 ms 40056 KB Output is correct
63 Correct 224 ms 42660 KB Output is correct
64 Correct 5 ms 16988 KB Output is correct
65 Correct 4 ms 16988 KB Output is correct
66 Correct 5 ms 16988 KB Output is correct
67 Correct 5 ms 17104 KB Output is correct
68 Correct 5 ms 16988 KB Output is correct
69 Correct 5 ms 17200 KB Output is correct
70 Correct 5 ms 16988 KB Output is correct
71 Correct 6 ms 17240 KB Output is correct
72 Correct 5 ms 16988 KB Output is correct
73 Correct 6 ms 16988 KB Output is correct
74 Correct 133 ms 49540 KB Output is correct
75 Correct 120 ms 39116 KB Output is correct
76 Correct 126 ms 39372 KB Output is correct
77 Correct 128 ms 41676 KB Output is correct
78 Correct 92 ms 48584 KB Output is correct
79 Correct 72 ms 39908 KB Output is correct
80 Correct 122 ms 45584 KB Output is correct
81 Correct 154 ms 51528 KB Output is correct
82 Correct 184 ms 54856 KB Output is correct
83 Correct 185 ms 58312 KB Output is correct
84 Correct 96 ms 41932 KB Output is correct
85 Correct 170 ms 56212 KB Output is correct
86 Correct 95 ms 29316 KB Output is correct
87 Correct 240 ms 43520 KB Output is correct
88 Correct 255 ms 43948 KB Output is correct
89 Correct 318 ms 45764 KB Output is correct
90 Correct 209 ms 53256 KB Output is correct
91 Correct 215 ms 51336 KB Output is correct
92 Correct 323 ms 49412 KB Output is correct
93 Correct 266 ms 55168 KB Output is correct
94 Correct 377 ms 58656 KB Output is correct
95 Correct 331 ms 62224 KB Output is correct
96 Correct 283 ms 46140 KB Output is correct
97 Correct 313 ms 51808 KB Output is correct