oj.uz

답안 #576582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
576582 2022-06-13T08:14:56 Z pooyashams 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -