oj.uz

Submission #150487

# Submission time Handle Problem Language Result Execution time Memory
150487 2019-09-01T08:30:41 Z 서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 196964 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];
vector <pii> son[100050];
int par[100050][17][2];
int dep[100050];
int col[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]);
		}
		son[n].push_back(it);
		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 dis[100050];
void DFS2(int n, int c) {
	dis[n] = -INF;
	if (col[n] == c) dis[n] = INF;
	for (auto it : son[n]) {
		DFS2(it.second, c);
		dis[n] = max(dis[n], min(dis[it.second], it.first));
	}
}
void DFS3(int n) {
	for (auto it : son[n]) {
		dis[it.second] = max(dis[it.second], min(dis[n], it.first));
		DFS3(it.second);
	}
}

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

int u[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 < 17; 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;

	for (i = 0; i < K && i < 400; i++) {
		int c = u[i];
		ch[c] = i;
		for (j = 0; j < N; j++) dis[j] = -1;
		DFS2(0, c);
		DFS3(0);

		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:210: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:223:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < Vl.size(); i++) {
                  ~~^~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3819 ms 196964 KB Output is correct
2 Correct 4067 ms 196832 KB Output is correct
3 Correct 4483 ms 196832 KB Output is correct
4 Correct 3816 ms 196836 KB Output is correct
5 Correct 4395 ms 196836 KB Output is correct
6 Correct 4723 ms 196832 KB Output is correct
7 Correct 4314 ms 196836 KB Output is correct
8 Correct 4198 ms 196924 KB Output is correct
9 Correct 4456 ms 196832 KB Output is correct
10 Correct 4441 ms 196832 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7552 KB Output is correct
2 Correct 11 ms 7552 KB Output is correct
3 Correct 284 ms 36836 KB Output is correct
4 Correct 399 ms 36964 KB Output is correct
5 Correct 456 ms 36832 KB Output is correct
6 Correct 825 ms 37088 KB Output is correct
7 Correct 1185 ms 37344 KB Output is correct
8 Correct 2564 ms 38112 KB Output is correct
9 Execution timed out 5074 ms 39772 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7552 KB Output is correct
2 Correct 11 ms 7552 KB Output is correct
3 Correct 3819 ms 196964 KB Output is correct
4 Correct 4067 ms 196832 KB Output is correct
5 Correct 4483 ms 196832 KB Output is correct
6 Correct 3816 ms 196836 KB Output is correct
7 Correct 4395 ms 196836 KB Output is correct
8 Correct 4723 ms 196832 KB Output is correct
9 Correct 4314 ms 196836 KB Output is correct
10 Correct 4198 ms 196924 KB Output is correct
11 Correct 4456 ms 196832 KB Output is correct
12 Correct 4441 ms 196832 KB Output is correct
13 Correct 284 ms 36836 KB Output is correct
14 Correct 399 ms 36964 KB Output is correct
15 Correct 456 ms 36832 KB Output is correct
16 Correct 825 ms 37088 KB Output is correct
17 Correct 1185 ms 37344 KB Output is correct
18 Correct 2564 ms 38112 KB Output is correct
19 Execution timed out 5074 ms 39772 KB Time limit exceeded
20 Halted 0 ms 0 KB -