oj.uz

Submission #150455

# Submission time Handle Problem Language Result Execution time Memory
150455 2019-09-01T08:26:35 Z From The Sky(#3630, WhipppedCream, top34051, zoomswk) Trip to the Galapagos Islands (FXCUP4_island) C++17
0 / 100
 5000 ms 15972 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int mlog = 18;

int n, m, k;
int a[maxn], act[maxn];
int head[maxn];
vector<pair<int,int>> way[maxn];
int h[maxn];
vector<int> ord;
int mx[maxn];
int res[1005][1005];

void dfs(int u, int last) {
	h[u] = h[last] + 1;
	for(auto tmp : way[u]) {
		int v = tmp.first, val = tmp.second;
		if(v == last) continue;
		dfs(v, u);
	}
	ord.push_back(u);
}

int findhead(int x) {
	if(x==head[x]) return x;
	return head[x] = findhead(head[x]);
}

void solve() {
	for(int x=1;x<=k;++x) {
		for(int u=1;u<=n;++u) {
			mx[u] = 0;
			if(a[u] == x) mx[u] = m;
		}
		for(int i=0;i<n;++i) {
			int u = ord[i];
			for(auto tmp : way[u]) {
				int v = tmp.first, val = tmp.second;
				int nxt = min(mx[u], val);
				if(h[v] < h[u] && mx[v] < nxt) mx[v] = nxt;
			}
		}
		for(int i=n-1;i>=0;--i) {
			int u = ord[i];
			for(auto tmp : way[u]) {
				int v = tmp.first, val = tmp.second;
				int nxt = min(mx[u], val);
				if(h[v] >= h[u] && mx[v] < nxt) mx[v] = nxt;
			}
		}
		for(int u=1;u<=n;u++) {
			if(res[x][a[u]] < mx[u]) res[x][a[u]] = mx[u];
		}
	}
}

void Init(int K, vector<int> col, vector<int> s, vector<int> e) {
	n = col.size(); m = s.size(); k = K;
	for(int i=1;i<=n;++i) a[i] = col[i-1] + 1;
	for(int i=1;i<=n;++i) head[i] = i;
	for(int i=m;i>=1;--i) {
		int x = s[i-1] + 1, y = e[i-1] + 1;
		if(findhead(x) != findhead(y)) {
			head[findhead(x)] = findhead(y);
			way[x].push_back({y, i});
			way[y].push_back({x, i});
		}
	}
	dfs(1,0);
	solve();
}

int Separate(int x, int y) {
	++x; ++y;
	return res[x][y];
}

Compilation message

island.cpp: In function 'void dfs(int, int)':
island.cpp:19:22: warning: unused variable 'val' [-Wunused-variable]
   int v = tmp.first, val = tmp.second;
                      ^~~

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5100 ms 15972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct
3 Correct 228 ms 14308 KB Output is correct
4 Correct 373 ms 14432 KB Output is correct
5 Correct 640 ms 14436 KB Output is correct
6 Correct 923 ms 14436 KB Output is correct
7 Correct 1635 ms 14684 KB Output is correct
8 Correct 3562 ms 15204 KB Output is correct
9 Execution timed out 5098 ms 15584 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct
3 Execution timed out 5100 ms 15972 KB Time limit exceeded
4 Halted 0 ms 0 KB -