oj.uz

Submission #536011

# Submission time Handle Problem Language Result Execution time Memory
536011 2022-03-12T06:21:00 Z akhan42 Uzastopni (COCI15_uzastopni) C++17
88 / 160
 40 ms 50252 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];
vi* gl_gr;
vi att;


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

	for(int nb: gl_gr[node]) {
		if(!att[nb])
			dfs2(nb);
	}
}


vii dfs(int node = 0) {
	vi loc_gr[100];

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

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

	att.assign(100, false);
	gl_gr = loc_gr;

	dfs2(jokes[node]);
	vii links;

	forbn(l, 0, jokes[node] + 1)
		if(att[l])
			forbn(r, jokes[node], 100)
				if(att[r])
					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
88.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Runtime error 1 ms 988 KB Execution killed with signal 6
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 692 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Incorrect 8 ms 820 KB Output isn't correct
12 Runtime error 4 ms 1492 KB Execution killed with signal 6
13 Runtime error 4 ms 1472 KB Execution killed with signal 11
14 Runtime error 38 ms 50252 KB Execution killed with signal 11
15 Runtime error 37 ms 50180 KB Execution killed with signal 11
16 Runtime error 40 ms 50252 KB Execution killed with signal 11
17 Runtime error 4 ms 1492 KB Execution killed with signal 6
18 Runtime error 5 ms 1492 KB Execution killed with signal 11
19 Correct 9 ms 852 KB Output is correct
20 Correct 8 ms 880 KB Output is correct