oj.uz

답안 #150375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150375 2019-09-01T08:15:11 Z 서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui) 갈라파고스 여행 (FXCUP4_island) C++17
31 / 100
 5000 ms 75488 KB 
#include "island.h"

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

int r[100050];
int sz[100050][2];
int root(int x) {
	return (x == r[x]) ? x : (r[x] = root(r[x]));
}

vector <pair<pii, int>> Ve;
vector <pii> conn[100050];
int par[100050][17][2];
int dep[100050];

int tus;
int lr[100050][2];
bool dchk[100050];
void DFS(int n) {
	lr[n][0] = ++tus;
	dchk[n] = true;
	for (auto it : conn[n]) {
		if (dchk[it.second]) continue;
		int nn = it.second;
		par[nn][0][0] = n;
		par[nn][0][1] = it.first;
		for (int i = 1; i < 17; i++) {
			int p = par[nn][i - 1][0];
			par[nn][i][0] = par[p][i - 1][0];
			par[nn][i][1] = min(par[p][i - 1][1], par[nn][i - 1][1]);
		}
		dep[nn] = dep[n] + 1;
		DFS(nn);
	}

	lr[n][1] = tus;
}

pii upnode(int a, int c) {
	int mn = INF;
	for (int i = 16; i >= 0; i--) {
		if (c & (1 << i)) {
			mn = min(mn, par[a][i][1]);
			a = par[a][i][0];
		}
	}
	return pii(a, mn);
}
int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);

	int c = dep[b] - dep[a];
	b = upnode(b, c).first;

	if (a == b) return a;

	for (int i = 16; i >= 0; i--) {
		if (par[a][i][0] != par[b][i][0]) {
			a = par[a][i][0];
			b = par[b][i][0];
		}
	}
	return par[a][0][0];
}

int ch[100050]; // answer array
int ans[305][100050];
int col[100050];
vector <int> Vc[100050];

int u[100050];
int dis[100050];
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	int N = F.size(), M = S.size(), i, j;

	for (i = 0; i < N; i++) col[i] = F[i];
	for (i = 0; i < N; i++) Vc[F[i]].push_back(i);

	for (i = 0; i < N; i++) r[i] = i;
	for (i = M - 1; i >= 0; i--) {
		int t1 = S[i], t2 = E[i];
		if (root(t1) == root(t2)) continue;
		int r1 = root(t1), r2 = root(t2);
		r[r1] = r2;
		Ve.emplace_back(pii(t1, t2), i);
		conn[t1].emplace_back(i, t2);
		conn[t2].emplace_back(i, t1);
	}
	for (i = 0; i < 20; i++) {
		par[0][i][0] = 0;
		par[0][i][1] = INF;
	}
	DFS(0);
	
	for (i = 0; i < K; i++) u[i] = i;
	sort(u, u + K, [](int a, int b) {
		if (Vc[a].size() != Vc[b].size()) return Vc[a].size() > Vc[b].size();
		return a > b;
	});

	for (i = 0; i < K; i++) ch[i] = -1;

	priority_queue <pii> Hx;
	for (i = 0; i < K && i < 100; i++) {
		int c = u[i];
		ch[c] = i;
		for (j = 0; j < N; j++) dis[j] = -1;
		for (auto it : Vc[c]) {
			dis[it] = INF;
			Hx.emplace(INF, it);
		}
		while (!Hx.empty()) {
			pii u = Hx.top();
			Hx.pop();
			if (dis[u.second] != u.first) continue;
			for (auto it : conn[u.second]) {
				pii u2 = pii(min(u.first, it.first), it.second);
				if (dis[u2.second] < u2.first) {
					dis[u2.second] = u2.first;
					Hx.push(u2);
				}
			}
		}
		for (j = 0; j < K; j++) ans[i][j] = -1;
		for (j = 0; j < N; j++) ans[i][F[j]] = max(ans[i][F[j]], dis[j]);
	}

	for (i = 0; i < N; i++) {
		r[i] = i;
		sz[i][0] = sz[i][1] = 0;
	}
}

int ispar(int a, int b) {
	if (dep[a] <= dep[b]) return -INF;

	pii u = upnode(a, dep[a] - dep[b]);
	if (u.first == b) return u.second;
	else return -INF;
}

int Separate(int A, int B){
	if (ch[A] >= 0) return ans[ch[A]][B] + 1;
	if (ch[B] >= 0) return ans[ch[B]][A] + 1;

	vector <int> Vl;
	vector <int> Vl2;
	vector <int> Vu;
	for (auto it : Vc[A]) Vl.push_back(it);
	for (auto it : Vc[B]) Vl.push_back(it);
	sort(all(Vl), [](int a, int b) {
		return lr[a][0] < lr[b][0];
	});
	Vl.erase(unique(all(Vl)), Vl.end());

	for (int i = 0; i + 1 < Vl.size(); i++) Vl2.push_back(lca(Vl[i], Vl[i + 1]));
	for (auto it : Vl) Vl2.push_back(it);

	sort(all(Vl2), [](int a, int b) {
		return lr[a][0] < lr[b][0];
	});
	Vl2.erase(unique(all(Vl2)), Vl2.end());
	Vl = Vl2;

	Vu.clear();
	Vu.push_back(Vl[0]);

	vector <pair<int, pii>> Vet;
	for (int i = 1; i < Vl.size(); i++) {
		int rv;
		
		while (1) {
			rv = ispar(Vl[i], Vu.back());
			if (rv != -INF) break;
			Vu.pop_back();
		}
		
		Vet.emplace_back(rv, pii(Vl[i], Vu.back()));
		Vu.push_back(Vl[i]);
	}
	sort(all(Vet));
	reverse(all(Vet));

	for (auto it : Vl) {
		r[it] = it;
		sz[it][0] = sz[it][1] = 0;
		if (col[it] == A) sz[it][0] = 1;
		if (col[it] == B) sz[it][1] = 1;
	}

	for (auto it : Vet) {
		int r1 = root(it.second.first), r2 = root(it.second.second);
		if (r1 == r2) continue;

		sz[r1][0] += sz[r2][0];
		sz[r1][1] += sz[r2][1];
		r[r2] = r1;
		if (sz[r1][0] && sz[r1][1]) return it.first + 1;
	}
	return 0;
}

Compilation message

island.cpp:25:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 
island.cpp:26:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")  
 
island.cpp: In function 'int Separate(int, int)':
island.cpp:206:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < Vl.size(); i++) Vl2.push_back(lca(Vl[i], Vl[i + 1]));
                  ~~~~~~^~~~~~~~~~~
island.cpp:219:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < Vl.size(); i++) {
                  ~~^~~~~~~~~~~
island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:140:16: warning: iteration 17 invokes undefined behavior [-Waggressive-loop-optimizations]
   par[0][i][0] = 0;
   ~~~~~~~~~~~~~^~~
island.cpp:139:16: note: within this loop
  for (i = 0; i < 20; i++) {
              ~~^~~~

Subtask #1
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3554 ms 75364 KB Output is correct
2 Correct 4141 ms 75384 KB Output is correct
3 Correct 4122 ms 75360 KB Output is correct
4 Correct 3317 ms 75460 KB Output is correct
5 Correct 3587 ms 75360 KB Output is correct
6 Correct 4270 ms 75360 KB Output is correct
7 Correct 4067 ms 75488 KB Output is correct
8 Correct 3359 ms 75364 KB Output is correct
9 Correct 4070 ms 75364 KB Output is correct
10 Correct 3351 ms 75408 KB Output is correct

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 9 ms 5120 KB Output is correct
3 Correct 309 ms 33124 KB Output is correct
4 Correct 628 ms 32992 KB Output is correct
5 Correct 1082 ms 32868 KB Output is correct
6 Correct 1808 ms 33000 KB Output is correct
7 Correct 3672 ms 33380 KB Output is correct
8 Execution timed out 5099 ms 33428 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 9 ms 5120 KB Output is correct
3 Correct 3554 ms 75364 KB Output is correct
4 Correct 4141 ms 75384 KB Output is correct
5 Correct 4122 ms 75360 KB Output is correct
6 Correct 3317 ms 75460 KB Output is correct
7 Correct 3587 ms 75360 KB Output is correct
8 Correct 4270 ms 75360 KB Output is correct
9 Correct 4067 ms 75488 KB Output is correct
10 Correct 3359 ms 75364 KB Output is correct
11 Correct 4070 ms 75364 KB Output is correct
12 Correct 3351 ms 75408 KB Output is correct
13 Correct 309 ms 33124 KB Output is correct
14 Correct 628 ms 32992 KB Output is correct
15 Correct 1082 ms 32868 KB Output is correct
16 Correct 1808 ms 33000 KB Output is correct
17 Correct 3672 ms 33380 KB Output is correct
18 Execution timed out 5099 ms 33428 KB Time limit exceeded
19 Halted 0 ms 0 KB -