oj.uz

Submission #149637

# Submission time Handle Problem Language Result Execution time Memory
149637 2019-09-01T06:53:04 Z 서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 58232 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][20][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 < 20; 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 = 19; 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 = 19; 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 < 50; 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++) {
                  ~~^~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2611 ms 58108 KB Output is correct
2 Correct 2047 ms 58228 KB Output is correct
3 Correct 1931 ms 58208 KB Output is correct
4 Correct 2120 ms 58200 KB Output is correct
5 Correct 2118 ms 58212 KB Output is correct
6 Correct 1825 ms 58208 KB Output is correct
7 Correct 2273 ms 58232 KB Output is correct
8 Correct 2257 ms 58208 KB Output is correct
9 Correct 2179 ms 58212 KB Output is correct
10 Correct 1827 ms 57956 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 9 ms 5120 KB Output is correct
3 Correct 333 ms 35680 KB Output is correct
4 Correct 562 ms 35300 KB Output is correct
5 Correct 936 ms 35300 KB Output is correct
6 Correct 1811 ms 35428 KB Output is correct
7 Execution timed out 5102 ms 35424 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 9 ms 5120 KB Output is correct
3 Correct 2611 ms 58108 KB Output is correct
4 Correct 2047 ms 58228 KB Output is correct
5 Correct 1931 ms 58208 KB Output is correct
6 Correct 2120 ms 58200 KB Output is correct
7 Correct 2118 ms 58212 KB Output is correct
8 Correct 1825 ms 58208 KB Output is correct
9 Correct 2273 ms 58232 KB Output is correct
10 Correct 2257 ms 58208 KB Output is correct
11 Correct 2179 ms 58212 KB Output is correct
12 Correct 1827 ms 57956 KB Output is correct
13 Correct 333 ms 35680 KB Output is correct
14 Correct 562 ms 35300 KB Output is correct
15 Correct 936 ms 35300 KB Output is correct
16 Correct 1811 ms 35428 KB Output is correct
17 Execution timed out 5102 ms 35424 KB Time limit exceeded
18 Halted 0 ms 0 KB -