Submission #210174

#	Time	Username	Problem	Language	Result	Execution time	Memory
210174		ZwariowanyMarcin	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	38 ms	11512 KiB

uzastopni

#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep2(i, j, n) for (LL i = j; i <= n; ++i)
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define boost cin.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 1e4 + 10;
const int K = 110;
const int V = 100;

int n;
int a, b;
vector <int> v[N];
int prawo[N][K], lewo[N][K];
int c[N];

void dfs(int u) {
	vector <int> L, R;
	for (auto it : v[u]) {
		dfs(it);
		if (c[it] < c[u]) L.pb(it);
		if (c[it] > c[u]) R.pb(it);
	}
	prawo[u][c[u]] = 1;
	lewo[u][c[u]] = 1;
	sort(R.begin(), R.end(), [](int a, int b) {
		return c[a] < c[b];
	});
	sort(L.begin(), L.end(), [](int a, int b) {
		return c[a] > c[b];
	});
	for (auto it : R)
		rep(Left, c[u] + 1, V)
			rep(Right, Left, V)
				prawo[u][Right] |= (lewo[it][Left] & prawo[it][Right] & prawo[u][Left - 1]);
	
	for (auto it : L)
		rep(Left, 1, c[u] - 1)
			rep(Right, Left, c[u] - 1)
				lewo[u][Left] |= (lewo[it][Left] && prawo[it][Right] & lewo[u][Right + 1]);
}

int main() {
	scanf ("%d", &n);
	rep(i, 1, n) scanf ("%d", c + i);
	rep(i, 1, n - 1) {
		scanf ("%d%d", &a, &b);
		v[a].pb(b);
	}
	dfs(1);
	int L = 0;
	int R = 0;
	rep(i, 1, V) {
		L += lewo[1][i];
		R += prawo[1][i];
	}
	printf ("%d\n", L * R);
		
	return 0;
}

Compilation message (stderr)

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
uzastopni.cpp:56:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, n) scanf ("%d", c + i);
               ~~~~~~^~~~~~~~~~~~~
uzastopni.cpp:58:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160