oj.uz

답안 #536022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536022 2022-03-12T06:49:54 Z akhan42 Uzastopni (COCI15_uzastopni) C++17
120 / 160
 31 ms 3216 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define lc v << 1
#define rc (v << 1) + 1

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 10 * 1000 + 10;

vi gr[MX];
int jokes[MX];
bitset<100> gl_gr[100];
vi att;


void dfs2(int node) {
	att[node] = true;

	for(int nb = gl_gr[node]._Find_first(); nb < sz(gl_gr[node]); nb = gl_gr[node]._Find_next(nb)) {
		if(!att[nb])
			dfs2(nb);
	}
}


vii dfs(int node = 0) {
	vii edges;

	for(int nb: gr[node]) {
		vii links = dfs(nb);

		for(ii p: links) {
			if(jokes[node] < jokes[nb])
				edges.eb(p.F - 1, p.S);
			else if(jokes[node] > jokes[nb])
				edges.eb(p.S + 1, p.F);
		}
	}

	att.assign(100, false);
	forn(i, 100)
		gl_gr[i].reset();
	for(ii p: edges)
		gl_gr[p.F][p.S] = 1;

	dfs2(jokes[node]);

	vii links;
	vi left, right;
	forbn(l, 0, jokes[node] + 1) if(att[l]) left.pb(l);
	forbn(r, jokes[node], 100) if(att[r]) right.pb(r);

	for(int l: left)
		for(int r: right)
			links.eb(l, r);

	return links;
}



void solve() {
	int n;
	cin >> n;

	forn(i, n) {
		cin >> jokes[i];
		jokes[i]--;
	}

	forn(_, n - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		gr[a].pb(b);
	}

	vii links = dfs(0);

	cout << sz(links);
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("triangles.in", "r", stdin);
//	freopen("triangles.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

Subtask #1
120.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 564 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 1 ms 560 KB Output is correct
10 Correct 1 ms 560 KB Output is correct
11 Incorrect 11 ms 852 KB Output isn't correct
12 Incorrect 12 ms 852 KB Output isn't correct
13 Correct 12 ms 864 KB Output is correct
14 Incorrect 31 ms 3156 KB Output isn't correct
15 Incorrect 29 ms 3156 KB Output isn't correct
16 Incorrect 31 ms 3216 KB Output isn't correct
17 Correct 10 ms 852 KB Output is correct
18 Correct 10 ms 864 KB Output is correct
19 Correct 12 ms 816 KB Output is correct
20 Correct 10 ms 812 KB Output is correct