oj.uz

Submission #576582

# Submission time Handle Problem Language Result Execution time Memory
576582 2022-06-13T08:14:56 Z pooyashams Swapping Cities (APIO20_swap) C++14
7 / 100
 2000 ms 23380 KB 
#include "swap.h"
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int lgmx = 18;
const int inf = 1e9+69;

struct edge
{
	int x, y, z;
	inline bool operator<(const edge& o) const
	{
		return z < o.z;
	}
} edgs[maxn];

int N, M;

vector<int> comp[maxn];
int root[maxn];
bool ispath[maxn];
int fnp[maxn];
pii sars[maxn];

int epar[maxn];
int dpar[maxn];
vector<int> kids[maxn];

inline void invldp(int r, int z)
{
	for(int u: comp[r])
	{
		ispath[u] = false;
		fnp[u] = z;
	}
}

inline bool isin(int x, pii p)
{
	return x == p.first or x == p.second;
}

inline void mrg(int x, int y, int z)
{
	if(comp[root[x]].size() < comp[root[y]].size())
		swap(x, y);
	int rx = root[x];
	int ry = root[y];
	if(rx == ry)
	{
		if(ispath[rx])
			invldp(rx, z);
	}
	else
	{
		if( ispath[rx] and ispath[ry] and isin(x, sars[rx]) and isin(y, sars[ry]) )
		{
			int a = sars[rx].first^sars[rx].second ^ x;
			int b = sars[ry].first^sars[ry].second ^ y;
			sars[rx] = pii(a, b);
		}
		else
		{
			if(ispath[rx])
				invldp(rx, z);
			if(ispath[ry])
				invldp(ry, z);
		}
		epar[ry] = z;
		dpar[ry] = rx;
		for(int u: comp[ry])
		{
			root[y] = rx;
			comp[rx].push_back(u);
		}
		comp[ry].clear();
	}
}

int tin[maxn];
int tout[maxn];
int timer = 0;

void dfs(int v)
{
	tin[v] = timer++;
	for(int u: kids[v])
		dfs(u);
	tout[v] = timer;
}

inline bool isanc(int x, int y)
{
	return (tin[x] <= tin[y] and tout[y] <= tout[x]);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
	::N = N;
	::M = M;
	for(int i = 0; i < N; i++)
	{
		root[i] = i;
		comp[i].push_back(i);
		ispath[i] = true;
		fnp[i] = inf;
		sars[i] = pii(i, i);
		dpar[i] = i;
	}
	for(int i = 0; i < M; i++)
		edgs[i] = {V[i], U[i], W[i]};
	sort(edgs, edgs+M);
	for(int i = 0; i < M; i++)
	{
		int x = edgs[i].x;
		int y = edgs[i].y;
		int z = edgs[i].z;
		mrg(x, y, z);
	}
	int r = 0;
	for(int i = 0; i < N; i++)
	{
		if(dpar[i] != i)
			kids[dpar[i]].push_back(i);
		else
			r = i;
	}
	//cerr << r << endl;
	dfs(r);
}

int getMinimumFuelCapacity(int x, int y)
{
	int ans = max(fnp[x], fnp[y]);
	int v = x;
	while(!isanc(v, y))
	{
		ans = max(ans, epar[v]);
		v = dpar[v];
	}
	v = y;
	while(!isanc(v, x))
	{
		ans = max(ans, epar[v]);
		v = dpar[v];
	}
	if(ans == inf)
		return -1;
	return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9744 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9744 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 55 ms 18124 KB Output is correct
10 Correct 69 ms 20052 KB Output is correct
11 Correct 67 ms 19792 KB Output is correct
12 Correct 69 ms 20356 KB Output is correct
13 Execution timed out 2072 ms 20628 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9744 KB Output is correct
3 Correct 108 ms 23020 KB Output is correct
4 Correct 107 ms 23308 KB Output is correct
5 Correct 120 ms 23264 KB Output is correct
6 Correct 105 ms 23148 KB Output is correct
7 Correct 116 ms 23380 KB Output is correct
8 Correct 128 ms 23028 KB Output is correct
9 Correct 107 ms 23220 KB Output is correct
10 Correct 110 ms 22880 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9744 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9744 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 55 ms 18124 KB Output is correct
11 Correct 69 ms 20052 KB Output is correct
12 Correct 67 ms 19792 KB Output is correct
13 Correct 69 ms 20356 KB Output is correct
14 Execution timed out 2072 ms 20628 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9744 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9744 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 55 ms 18124 KB Output is correct
10 Correct 69 ms 20052 KB Output is correct
11 Correct 67 ms 19792 KB Output is correct
12 Correct 69 ms 20356 KB Output is correct
13 Execution timed out 2072 ms 20628 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9744 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9744 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 55 ms 18124 KB Output is correct
11 Correct 69 ms 20052 KB Output is correct
12 Correct 67 ms 19792 KB Output is correct
13 Correct 69 ms 20356 KB Output is correct
14 Execution timed out 2072 ms 20628 KB Time limit exceeded
15 Halted 0 ms 0 KB -