oj.uz

답안 #148183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
148183 2019-08-31T16:47:52 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) 갈라파고스 여행 (FXCUP4_island) C++17
0 / 100
 5000 ms 82400 KB 
#include "island.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define pii pair<int,int>

int Col[101000], n, m, UF[101000], par[101000][20], Mx[101000][20], Dep[101000], Num[101000], Ed[101000], cnt, D[101000], vis[101000], Fnum[101000];
vector<int>E[101000], L[101000], FF[101000], ZZ[101000], Fre;
int DD[1010][101000], TH = 1;
int Find(int a) {
	if (a == UF[a])return a;
	return UF[a] = Find(UF[a]);
}
void Add_Edge(int a, int b, int c) {
	E[a].push_back(b);
	E[b].push_back(a);
	L[a].push_back(c);
	L[b].push_back(c);
}
void DFS(int a, int pp) {
	Num[a] = ++cnt;
	par[a][0] = pp;
	for (int i = 0; i < 18; i++) {
		par[a][i + 1] = par[par[a][i]][i];
		Mx[a][i + 1] = max(Mx[par[a][i]][i], Mx[a][i]);
	}
	for (int i = 0; i < E[a].size(); i++) {
		int x = E[a][i];
		if (x == pp)continue;
		Mx[x][0] = L[a][i];
		Dep[x] = Dep[a] + 1;
		DFS(x, a);
	}
	Ed[a] = cnt;
}


void Init(int K, std::vector<int> F, std::vector<int> A, std::vector<int> B){
	int i, j;
	n = F.size(), m = A.size();
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());
	for (i = 1; i <= n; i++) {
		UF[i] = i;
		Col[i] = F[i - 1] + 1;
		FF[Col[i]].push_back(i);
	}
	vector<int>U;
	for (i = 0; i < m; i++) {
		int a = A[i] + 1, b = B[i] + 1;
		U.push_back(i);
		if (Find(a) != Find(b)) {
			UF[Find(a)] = Find(b);
			Add_Edge(a, b, i+1);
		}
	}
	DFS(1, 0);
	for (i = 1; i <= n; i++) {
		if (FF[i].size() >= TH) {
			Fre.push_back(i);
			priority_queue<pii>PQ;
			for (j = 1; j <= n; j++) {
				D[j] = 1e9;
				vis[j] = 0;
			}
			for (auto &x : FF[i]) {
				PQ.push({ 0,x });
				D[x] = 0;
			}
			while (!PQ.empty()) {
				pii tp = PQ.top();
				PQ.pop();
				int x = tp.second;
				if (vis[x])continue;
				vis[x] = 1;
				for (j = 0; j < E[x].size(); j++) {
					int d = max(D[x], L[x][j]), t = E[x][j];
					if (D[t] > d) {
						D[t] = d;
						PQ.push({ -d, t });
					}
				}
			}
			int cur = Fre.size() - 1;
			Fnum[i] = cur;
			for (j = 1; j <= n; j++) {
				DD[cur][j] = 1e9;
			}
			for (j = 1; j <= n; j++)DD[cur][Col[j]] = min(DD[cur][Col[j]], D[j]);
		}
	}
}

int Separate(int A, int B){
	A++, B++;
	if (FF[A].size() >= TH)return m + 1 - DD[Fnum[A]][B];
	if (FF[B].size() >= TH)return m + 1 - DD[Fnum[B]][A];
}

Compilation message

island.cpp: In function 'void DFS(int, int)':
island.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E[a].size(); i++) {
                  ~~^~~~~~~~~~~~~
island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (FF[i].size() >= TH) {
       ~~~~~~~~~~~~~^~~~~
island.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < E[x].size(); j++) {
                 ~~^~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (FF[A].size() >= TH)return m + 1 - DD[Fnum[A]][B];
      ~~~~~~~~~~~~~^~~~~
island.cpp:99:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (FF[B].size() >= TH)return m + 1 - DD[Fnum[B]][A];
      ~~~~~~~~~~~~~^~~~~
island.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5105 ms 82400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 9880 KB Output is correct
2 Correct 22 ms 9984 KB Output is correct
3 Correct 411 ms 43636 KB Output is correct
4 Correct 982 ms 46940 KB Output is correct
5 Correct 1455 ms 52760 KB Output is correct
6 Correct 2446 ms 62692 KB Output is correct
7 Execution timed out 5099 ms 78080 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 9880 KB Output is correct
2 Correct 22 ms 9984 KB Output is correct
3 Execution timed out 5105 ms 82400 KB Time limit exceeded
4 Halted 0 ms 0 KB -