oj.uz

답안 #847547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
847547 2023-09-09T20:51:07 Z TB_ Uzastopni (COCI15_uzastopni) C++17
80 / 160
 139 ms 17516 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 &v : adj[u]){
        if(v == last) continue;
        vector<bitset<102>> res = dfs(v, u);
        fo(i, 102) 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
80.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 2 ms 604 KB Output isn't correct
5 Incorrect 2 ms 604 KB Output isn't correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 704 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Incorrect 121 ms 1112 KB Output isn't correct
12 Incorrect 123 ms 1156 KB Output isn't correct
13 Correct 132 ms 1128 KB Output is correct
14 Incorrect 137 ms 17500 KB Output isn't correct
15 Incorrect 138 ms 17408 KB Output isn't correct
16 Incorrect 139 ms 17516 KB Output isn't correct
17 Correct 131 ms 1128 KB Output is correct
18 Correct 126 ms 1116 KB Output is correct
19 Incorrect 117 ms 1312 KB Output isn't correct
20 Incorrect 116 ms 1116 KB Output isn't correct