답안 #251846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251846 2020-07-22T11:19:47 Z ne4eHbKa Uzastopni (COCI15_uzastopni) C++17
56 / 160
500 ms 16888 KB
//{ <defines>
#include <bits/stdc++.h>
using namespace std;

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

int md = 998244353;

inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}

int m_bpow(ll A, ll b) {
    int a = A % md;
    ll ans = 1;
    for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
        (ans *= ans) %= md;
        if(p & b)
            (ans *= a) %= md;
    }
    re ans;
}

//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 1e4 + 5;
const int M = 101;

typedef bitset<M> bt;

int n;
int vl[N];
bt f[N][M], z[M];
list<int> g[N];

void rec(int v) {
    fo(M) z[i].reset(), z[i].set(i), f[v][i] = z[i];
    for(int u : g[v]) rec(u);
    for(int u : g[v]) {
        for(int i = 0; i <= 100; ++i)
            z[i] |= f[u][i];
    }
    for(int t = 0; t <= 100; ++t) {
        for(int i = 0; i <= 100; ++i) {
            for(int j = 0; j <= 100; ++j) {
                if(z[i][t] && z[t][j]) z[i].set(j);
            }
        }
    }
    int u = vl[v];
    for(int l = 0; l <= u; ++l) {
        ifn(z[l][u]) continue;
        for(int r = u + 1; r <= 100; ++r) {
            ifn(z[u + 1][r]) continue;
            f[v][l].set(r);
        }
    }
}

void solve() {
    cin >> n;
    fo(n) cin >> vl[i], --vl[i], g[i].clear();
    fo(n - 1) {
        int x, y;
        cin >> x >> y;
        g[x - 1].pb(y - 1);
    }
    rec(0);
    int ans = 0;
    for(int i = 0; i < 100; ++i)
        for(int j = i + 1; j <= 100; ++j)
            if(f[0][i][j]) ++ans;
    cout << ans << endl;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    for(int test = 1; test <= tests; ++test) {
		cerr << "case #" << test << endl;
        solve();
        cerr << endl;
    }
#else
//    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#endif
    return 0;
}

Compilation message

uzastopni.cpp: In function 'int m_bpow(ll, ll)':
uzastopni.cpp:50:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 640 KB Output isn't correct
2 Correct 73 ms 640 KB Output is correct
3 Correct 81 ms 760 KB Output is correct
4 Incorrect 82 ms 796 KB Output isn't correct
5 Incorrect 107 ms 760 KB Output isn't correct
6 Correct 106 ms 768 KB Output is correct
7 Correct 113 ms 916 KB Output is correct
8 Correct 109 ms 800 KB Output is correct
9 Correct 107 ms 760 KB Output is correct
10 Correct 105 ms 760 KB Output is correct
11 Execution timed out 1086 ms 6024 KB Time limit exceeded
12 Execution timed out 1082 ms 6136 KB Time limit exceeded
13 Execution timed out 1094 ms 6008 KB Time limit exceeded
14 Execution timed out 1082 ms 16764 KB Time limit exceeded
15 Execution timed out 1091 ms 16760 KB Time limit exceeded
16 Execution timed out 1033 ms 16888 KB Time limit exceeded
17 Execution timed out 1092 ms 6376 KB Time limit exceeded
18 Execution timed out 1095 ms 6352 KB Time limit exceeded
19 Execution timed out 1051 ms 2808 KB Time limit exceeded
20 Execution timed out 1096 ms 2876 KB Time limit exceeded