oj.uz

답안 #847554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
847554 2023-09-09T21:55:50 Z TB_ Uzastopni (COCI15_uzastopni) C++17
160 / 160
 153 ms 18008 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(ll i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

vl v;
vvl adj(10001);
    

vector<bitset<102>> dfs(int u, int last = -1){
    vector<bitset<102>> current(102);
    current[v[u]][v[u]] = 1;
    for(auto &ve : adj[u]){
        if(ve == last) continue;
        vector<bitset<102>> res = dfs(ve, u);
        fo(i, 102) {
            if(i == v[u]) continue;
            if(i<v[u]) current[i]|=res[i]<<(current.size()-v[u])>>(current.size()-v[u]);
            else current[i]|=res[i];
        }
    }
    fo(i, 101){
        for(int j = i; j<101; j++){
            if(!current[i][j]) continue;
            current[i] |= current[j+1];
        }
    }
    fo(i, 101){
        for(int j = i; j<101; j++){
            if(i>v[u] || j<v[u]) current[i][j] = 0;
        }
    }
    
    return current;
}

int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);

    int n, from, to;
    cin >> n;
    v.resize(n);
    fo(i, n) cin >> v[i];

    fo(i, n-1){
        cin >> from >> to;
        adj[--from].pb(--to);
        adj[to].pb(from);
    }

    vector<bitset<102>> res = dfs(0);
    ll ans = 0;
    fo(i, 101) ans += res[i].count();
    cout << ans;

    return 0;
}

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 122 ms 1116 KB Output is correct
12 Correct 123 ms 1112 KB Output is correct
13 Correct 123 ms 1112 KB Output is correct
14 Correct 145 ms 18008 KB Output is correct
15 Correct 153 ms 18008 KB Output is correct
16 Correct 141 ms 18008 KB Output is correct
17 Correct 126 ms 1112 KB Output is correct
18 Correct 125 ms 1112 KB Output is correct
19 Correct 117 ms 1188 KB Output is correct
20 Correct 113 ms 1112 KB Output is correct