Submission #366678

#TimeUsernameProblemLanguageResultExecution timeMemory
366678gmyuUzastopni (COCI15_uzastopni)C++14
160 / 160
52 ms23916 KiB
/* 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)

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 timeMemoryGrader output
Fetching results...