답안 #366678

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366678 2021-02-14T23:54:17 Z gmyu Uzastopni (COCI15_uzastopni) C++14
160 / 160
52 ms 23916 KB
/*
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;
      |               ^
# 결과 실행 시간 메모리 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