oj.uz

답안 #847550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
847550 2023-09-09T21:36:45 Z TB_ Uzastopni (COCI15_uzastopni) C++17
136 / 160
 144 ms 18012 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]) 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
136.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 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 856 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 126 ms 1116 KB Output is correct
12 Incorrect 128 ms 1116 KB Output isn't correct
13 Correct 126 ms 1112 KB Output is correct
14 Correct 144 ms 18012 KB Output is correct
15 Correct 140 ms 18012 KB Output is correct
16 Correct 142 ms 18012 KB Output is correct
17 Correct 128 ms 1180 KB Output is correct
18 Correct 139 ms 1372 KB Output is correct
19 Incorrect 121 ms 1188 KB Output isn't correct
20 Incorrect 121 ms 1116 KB Output isn't correct