Submission #366678

#	Time	Username	Problem	Language	Result	Execution time	Memory
366678		gmyu	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	52 ms	23916 KiB

uzastopni

/*
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;
      |               ^

• Subtask 1: 160 / 160