/*
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
uzastopni.cpp: In function 'int main()':
uzastopni.cpp:105:12: warning: unused variable 'j' [-Wunused-variable]
105 | int i, j, k;
| ^
uzastopni.cpp:105:15: warning: unused variable 'k' [-Wunused-variable]
105 | int i, j, k;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
876 KB |
Output is correct |
| 2 |
Correct |
1 ms |
876 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1016 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 11 |
Correct |
26 ms |
17516 KB |
Output is correct |
| 12 |
Correct |
24 ms |
17388 KB |
Output is correct |
| 13 |
Correct |
22 ms |
17388 KB |
Output is correct |
| 14 |
Correct |
48 ms |
23788 KB |
Output is correct |
| 15 |
Correct |
47 ms |
23788 KB |
Output is correct |
| 16 |
Correct |
52 ms |
23916 KB |
Output is correct |
| 17 |
Correct |
22 ms |
17388 KB |
Output is correct |
| 18 |
Correct |
22 ms |
17516 KB |
Output is correct |
| 19 |
Correct |
36 ms |
19948 KB |
Output is correct |
| 20 |
Correct |
36 ms |
19948 KB |
Output is correct |
