#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];
pair<int,int> par[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;
par[v] = {v, val};
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];
int v = par[u].first, val = par[u].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];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5100 ms |
18656 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
