Submission #964710

#	Time	Username	Problem	Language	Result	Execution time	Memory
964710		pcc	Uzastopni (COCI15_uzastopni)	C++17	120 / 160	28 ms	6124 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e4+10;

int N;
int arr[mxn];
vector<int> tree[mxn];
vector<int> lp[mxn],rp[mxn];
vector<int> lop[110],rop[110];
bitset<mxn> dl,dr;

void dfs(int now){
	for(auto &i:lop)i.clear();
	for(auto &i:rop)i.clear();
	for(auto nxt:tree[now]){
		dfs(nxt);
	}
	for(auto nxt:tree[now]){
		for(auto &i:lp[nxt]){
			for(auto &j:rp[nxt]){
				if(i>arr[now])rop[i].push_back(j);
				if(j<arr[now]){
					lop[j].push_back(i);
				}
			}
		}
	}
	dl.reset();
	dr.reset();
	dl[arr[now]] = dr[arr[now]] = 1;
	for(int i = arr[now];i+1<110;i++){
		if(dr[i]){
			rp[now].push_back(i);
			for(auto &j:rop[i+1])dr[j] = 1;
		}
	}
	for(int i = arr[now];i>0;i--){
		if(dl[i]){
			lp[now].push_back(i);
			for(auto &j:lop[i-1])dl[j] = 1;
		}
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
	}
	dfs(1);
	/*
	for(int i = 1;i<=N;i++){
		cout<<i<<":"<<endl;
		for(auto &j:lp[i])cout<<j<<',';cout<<endl;
		for(auto &j:rp[i])cout<<j<<',';cout<<endl;
	}

   */
	cout<<(lp[1].size())*(rp[1].size())<<endl;
}

• Subtask 1: 120 / 160