oj.uz

Submission #357743

# Submission time Handle Problem Language Result Execution time Memory
357743 2021-01-24T15:05:48 Z AriaH Swapping Cities (APIO20_swap) C++11
13 / 100
 434 ms 49488 KB 
/** Im the best because i work as hard as i possibly can **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 21;

struct edge
{
    int v, u, c;
} E[N];

bool cmp(edge a, edge b) { return a.c < b.c; }

int _n, ptr, D[N], par[N], ok[N], P[LOG][N], H[N], up[N];

vector < int > G[N];

int get(int x) { return (x == par[x]? x : par[x] = get(par[x])); }

void unify(int i)
{
    ++ ptr;
    D[E[i].v] ++;
    D[E[i].u] ++;
    int v = get(E[i].v), u = get(E[i].u);
    if(v == u)
    {
	ok[ptr] = 1;
	G[ptr].push_back(v);
	P[0][v] = par[v] = ptr;
	return;
    }
    ok[ptr] = max({ok[v], ok[u], int(D[E[i].v] > 2), int(D[E[i].u] > 2)});
    P[0][v] = P[0][u] = par[u] = par[v] = ptr;
    G[ptr].push_back(v);
    G[ptr].push_back(u);
}

void dfs(int v)
{
    if(ok[v] == 0) up[v] = up[P[0][v]];
    else up[v] = v;
    H[v] = H[P[0][v]] + 1;
    for(int T = 1; T < LOG; T ++)
	P[T][v] = P[T - 1][P[T - 1][v]];
    for(auto u : G[v])
	dfs(u);
}

int LCA(int v, int u)
{
    if(H[v] > H[u]) swap(u, v);
    int del = (H[u] - H[v]);
    for(int T = 0; T < LOG; T ++)
    {
	if(del >> T & 1)
	{
	    u = P[T][u];
	}
    }
    if(v == u) return v;
    for(int T = LOG - 1; ~T; T --)
    {
	if(P[T][v] != P[T][u])
	{
	    u = P[T][u];
	    v = P[T][v];
	}
    }
    return P[0][v];
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W)
{
    _n = n;
    ptr = n;
    for(int i = 1; i <= m; i ++)
    {
	E[i] = {V[i - 1], U[i - 1], W[i - 1]};
    }
    iota(par, par + N, 0);
    sort(E + 1, E + m + 1, cmp);
    for(int i = 1; i <= m; i ++)
    {
	unify(i);
    }
    dfs(ptr);
}

int getMinimumFuelCapacity(int u, int v)
{
    int lca = LCA(u, v);
    if(up[lca] == 0)
    {
	return -1;
    }
    return E[up[lca] - _n].c;
}

/*
case 1:
5 6
1 2 4
1 3 4
3 4 3
4 2 2
2 5 10
2 3 1
3
2 3
3 5
1 2
case 2:
3 2
1 2 5
1 3 5
1
2 3
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14316 KB Output is correct
2 Correct 10 ms 14188 KB Output is correct
3 Correct 10 ms 14188 KB Output is correct
4 Correct 10 ms 14316 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 135 ms 35948 KB Output is correct
10 Correct 160 ms 40812 KB Output is correct
11 Correct 157 ms 40172 KB Output is correct
12 Correct 167 ms 41708 KB Output is correct
13 Correct 131 ms 43244 KB Output is correct
14 Correct 147 ms 36076 KB Output is correct
15 Correct 345 ms 45044 KB Output is correct
16 Correct 347 ms 44312 KB Output is correct
17 Correct 356 ms 45776 KB Output is correct
18 Correct 403 ms 47568 KB Output is correct
19 Correct 109 ms 23660 KB Output is correct
20 Correct 359 ms 46056 KB Output is correct
21 Correct 361 ms 45476 KB Output is correct
22 Correct 359 ms 47184 KB Output is correct
23 Correct 428 ms 49044 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14316 KB Output is correct
2 Correct 10 ms 14188 KB Output is correct
3 Correct 379 ms 48268 KB Output is correct
4 Correct 395 ms 49488 KB Output is correct
5 Correct 434 ms 48768 KB Output is correct
6 Correct 388 ms 49356 KB Output is correct
7 Correct 405 ms 49256 KB Output is correct
8 Correct 390 ms 47896 KB Output is correct
9 Correct 384 ms 48904 KB Output is correct
10 Correct 398 ms 47780 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14316 KB Output is correct
2 Correct 10 ms 14188 KB Output is correct
3 Correct 10 ms 14188 KB Output is correct
4 Correct 10 ms 14316 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14188 KB Output is correct
10 Correct 11 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Incorrect 11 ms 14444 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14188 KB Output is correct
2 Correct 10 ms 14316 KB Output is correct
3 Correct 10 ms 14188 KB Output is correct
4 Correct 10 ms 14188 KB Output is correct
5 Correct 10 ms 14316 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 135 ms 35948 KB Output is correct
11 Correct 160 ms 40812 KB Output is correct
12 Correct 157 ms 40172 KB Output is correct
13 Correct 167 ms 41708 KB Output is correct
14 Correct 131 ms 43244 KB Output is correct
15 Correct 11 ms 14444 KB Output is correct
16 Correct 11 ms 14444 KB Output is correct
17 Incorrect 11 ms 14444 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14316 KB Output is correct
2 Correct 10 ms 14188 KB Output is correct
3 Correct 10 ms 14188 KB Output is correct
4 Correct 10 ms 14316 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 135 ms 35948 KB Output is correct
10 Correct 160 ms 40812 KB Output is correct
11 Correct 157 ms 40172 KB Output is correct
12 Correct 167 ms 41708 KB Output is correct
13 Correct 131 ms 43244 KB Output is correct
14 Correct 147 ms 36076 KB Output is correct
15 Correct 345 ms 45044 KB Output is correct
16 Correct 347 ms 44312 KB Output is correct
17 Correct 356 ms 45776 KB Output is correct
18 Correct 403 ms 47568 KB Output is correct
19 Correct 379 ms 48268 KB Output is correct
20 Correct 395 ms 49488 KB Output is correct
21 Correct 434 ms 48768 KB Output is correct
22 Correct 388 ms 49356 KB Output is correct
23 Correct 405 ms 49256 KB Output is correct
24 Correct 390 ms 47896 KB Output is correct
25 Correct 384 ms 48904 KB Output is correct
26 Correct 398 ms 47780 KB Output is correct
27 Correct 11 ms 14444 KB Output is correct
28 Correct 11 ms 14444 KB Output is correct
29 Incorrect 11 ms 14444 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14188 KB Output is correct
2 Correct 10 ms 14316 KB Output is correct
3 Correct 10 ms 14188 KB Output is correct
4 Correct 10 ms 14188 KB Output is correct
5 Correct 10 ms 14316 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 135 ms 35948 KB Output is correct
11 Correct 160 ms 40812 KB Output is correct
12 Correct 157 ms 40172 KB Output is correct
13 Correct 167 ms 41708 KB Output is correct
14 Correct 131 ms 43244 KB Output is correct
15 Correct 147 ms 36076 KB Output is correct
16 Correct 345 ms 45044 KB Output is correct
17 Correct 347 ms 44312 KB Output is correct
18 Correct 356 ms 45776 KB Output is correct
19 Correct 403 ms 47568 KB Output is correct
20 Correct 379 ms 48268 KB Output is correct
21 Correct 395 ms 49488 KB Output is correct
22 Correct 434 ms 48768 KB Output is correct
23 Correct 388 ms 49356 KB Output is correct
24 Correct 405 ms 49256 KB Output is correct
25 Correct 390 ms 47896 KB Output is correct
26 Correct 384 ms 48904 KB Output is correct
27 Correct 398 ms 47780 KB Output is correct
28 Correct 11 ms 14444 KB Output is correct
29 Correct 11 ms 14444 KB Output is correct
30 Incorrect 11 ms 14444 KB Output isn't correct
31 Halted 0 ms 0 KB -