oj.uz

Submission #537356

# Submission time Handle Problem Language Result Execution time Memory
537356 2022-03-15T03:23:43 Z Haruto810198 Capital City (JOI20_capital_city) C++17
30 / 100
 1989 ms 105356 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n, k;
vi edge[MAX];
int icity[MAX];

int ts;
int arr[MAX];
vi occ[MAX];

set<int> st;
int dpl[MAX], dpr[MAX];
int stl[MAX][20], str[MAX][20];
vector<pii> segs;
int res;

void dfs(int v, int pv){
	ts++;
	arr[ts] = icity[v];
	occ[arr[ts]].pb(ts);
	for(int i : edge[v]){
		if(i == pv) continue;
		dfs(i, v);
	}
}

inline pii query(int l, int r){
	int rk = __lg(r - l + 1);
	return mkp(min(stl[l][rk], stl[r - (1<<rk) + 1][rk]), max(str[l][rk], str[r -(1<<rk) + 1][rk]));
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;
	FOR(i, 1, n-1, 1){
		int u, v;
		cin>>u>>v;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	FOR(i, 1, n, 1){
		cin>>icity[i];
	}

	int root = 0;
	FOR(i, 1, n, 1){
		if(szof(edge[i]) == 1) root = i;
	}

	dfs(root, root);
	
	FOR(i, 1, n, 1){
		dpl[i] = dpr[i] = i;	
	}
	
	FOR(i, 1, n, 1){
		dpl[i] = occ[arr[i]].front();
		dpr[i] = occ[arr[i]].back();
		//cerr<<"["<<dpl[i]<<", "<<dpr[i]<<"]"<<endl;
	}

	FOR(owo, 1, 19, 1){
		// build stl, str
		FOR(i, 1, n, 1){
			stl[i][0] = dpl[i];
			str[i][0] = dpr[i];
		}

		FOR(j, 1, 19, 1){
			FOR(i, 1, n, 1){
				int ii = i + (1<<(j-1));
				if(ii <= n){
					stl[i][j] = min(stl[i][j-1], stl[ii][j-1]);
					str[i][j] = max(str[i][j-1], str[ii][j-1]);
				}
				else{
					stl[i][j] = stl[i][j-1];
					str[i][j] = str[i][j-1];
				}
			}
		}

		// update dpl, dpr
		FOR(i, 1, n, 1){
			pii Q = query(dpl[i], dpr[i]);
			dpl[i] = Q.F;
			dpr[i] = Q.S;
		}
	}
	
	FOR(i, 1, n, 1){
		//cerr<<"["<<dpl[i]<<", "<<dpr[i]<<"]"<<endl;
	}

	res = INF;
	FOR(i, 1, n, 1){
		segs.eb(dpl[i], dpr[i]);
	}
	sort(segs.begin(), segs.end(), [&](pii a, pii b){
		if(a.F == b.F) return (a.S > b.S);
		return (a.F < b.F);
	});
	
	vector<pii> stk;
	for(pii p : segs){
		if(stk.empty()) stk.pb(p);
		else if(stk.back().F <= p.F and p.S <= stk.back().S){
			stk.pop_back();
			stk.pb(p);
		}
		else{
			stk.pb(p);
		}
	}

	for(pii p : stk){
		st.clear();
		FOR(i, p.F, p.S, 1){
			st.insert(arr[i]);
		}
		res = min(res, szof(st));
	}

	cout<<res - 1<<'\n';
	
	return 0;

}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9732 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9732 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1840 ms 101948 KB Output is correct
2 Correct 1644 ms 105244 KB Output is correct
3 Correct 1869 ms 105356 KB Output is correct
4 Correct 1790 ms 105252 KB Output is correct
5 Correct 1645 ms 105184 KB Output is correct
6 Correct 1689 ms 105240 KB Output is correct
7 Correct 1634 ms 105180 KB Output is correct
8 Correct 1720 ms 105064 KB Output is correct
9 Correct 1652 ms 104564 KB Output is correct
10 Correct 1642 ms 104556 KB Output is correct
11 Correct 1707 ms 104696 KB Output is correct
12 Correct 1684 ms 104668 KB Output is correct
13 Correct 1707 ms 104628 KB Output is correct
14 Correct 1884 ms 104668 KB Output is correct
15 Correct 1989 ms 104680 KB Output is correct
16 Correct 1980 ms 104552 KB Output is correct
17 Correct 1871 ms 104692 KB Output is correct
18 Correct 1861 ms 104684 KB Output is correct
19 Correct 1858 ms 104724 KB Output is correct
20 Correct 1715 ms 104740 KB Output is correct
21 Correct 9 ms 9684 KB Output is correct

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9732 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -