# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
366678 | gmyu | Uzastopni (COCI15_uzastopni) | C++14 | 52 ms | 23916 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/COCI15_uzastopni
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
#include <bitset>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 10007
#define MAXE 100007
bool debug;
/** dp[v][l] is a bitset<101> which marks at node v, for a consecutive set starting from l, which r it can end with
* this is calculated by for each child node, what are the valid consecutive set available for that node, call it dp2[u]
* dp2[v] is the valie consecutive set, meaning that it contains t[v]
* this collection is named dplist
*/
int N;
int t[MAXV];
vi adjlist[MAXV];
bitset<101> dp[MAXV][101];
vii dp2[MAXV];
vi dplist[101];
void dfs(int v, int pv) {
for(auto u : adjlist[v]) {
if(u==pv) continue;
dfs(u, v);
}
/// collect dplist first
for(int i=1;i<=100;i++) dplist[i].clear();
for(auto u: adjlist[v]) {
if(u==pv) continue;
for(auto x : dp2[u]) {
dplist[x.ff].pb(x.ss);
}
}
/// build dp[v][l]
for(int le=100; le >=1; le--) {
if(le > t[v]) {
for(auto ri : dplist[le]) {
dp[v][le][ri]= 1; dp[v][le] |= dp[v][ri+1];
}
} else if(le==t[v]) {
dp[v][le][le] = 1; dp[v][le] |= dp[v][le+1];
} else { // le < t[v]
for(auto ri : dplist[le]) {
/// here we need to consider whether [le, ri] is a valid set if ri > t[v],
/// if ri itself is from direct child node and ri > t[u], it is covered in above le > t[v] case
/// if not, ri has a gap vs child node so can not be used independently and have to be used with numbers between le .. ri which is covered in subcase where ri < t[v]
if(ri>=t[v]) continue;
dp[v][le][ri]= 1; dp[v][le] |= dp[v][ri+1];
}
}
}
/// build dp2
for(int le=1; le<=t[v]; le++)
for(int ri=t[v]; ri<=100; ri++) {
if(dp[v][le][ri]==1) dp2[v].pb(mp(le,ri));
}
}
#define adjread {int a, b; cin >> a >> b; adjlist[a].pb(b); adjlist[b].pb(a); }
int main() {
debug = true;
ios_base::sync_with_stdio(false); cin.tie(0);
int i, j, k;
cin >> N ;
for(i=1; i<=N; i++) cin >> t[i];
for(i=1;i<N; i++) { adjread; }
dfs(1,0);
cout << sz(dp2[1]) << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |