oj.uz

답안 #246223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246223 2020-07-08T11:42:14 Z bibabas Uzastopni (COCI15_uzastopni) C++14
120 / 160
 34 ms 21624 KB 
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
 
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
 
using namespace std;
 
const ll INF = (ll)2e9;
const ll inf = (ll)2e18;
const ld eps = (ld)1e-8;
const ll mod = (ll)998244353;
const ll MAXN = (ll)1e4 + 1;
const ll MAXC = (ll)1e6 + 1;
const ll MAXE = (ll)1000;
const ll MAXLOG = 21;
const ll maxlen = (ll)1e5;
const ll asci = (ll)256;
const ll block = 480;
const ld PI = acos(-1);
const ld e = 2.7182818284;
 
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
 
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};

bool comp(const pii &v, const pii &u) {
    if (v.second < u.second) return 1;
    return 0;
}

vector<pii> graph[MAXN];
ll le[MAXN][101], re[MAXN][101];

void dfs(ll v, vi &a) {
    for (pii u : graph[v]) {
        dfs(u.first, a);
    }
    graph[v].push_back(mp(v, a[v]));
    sort(all(graph[v]), comp);
    le[v][a[v]] = 1, re[v][a[v]] = 1; 
    ll pos = 0;
    for (ll i = 0; i < graph[v].size(); ++i) {
        if (graph[v][i].first == v) pos = i;
    }
    for (ll i = pos + 1; i < graph[v].size(); ++i) {
        bool fnd = 0;
        for (ll j = 1; j <= 100; ++j) {
            if (le[graph[v][i].first][j] && re[v][j - 1]) fnd = 1;
        }
        for (ll j = 0; j <= 100; ++j) {
            re[v][j] |= re[graph[v][i].first][j] & fnd;
        }
    }
    for (ll i = pos - 1; i >= 0; --i) {
        bool fnd = 0;
        for (ll j = 0; j < 100; ++j) {
            if (re[graph[v][i].first][j] && le[v][j + 1]) fnd = 1;
        }
        for (ll j = 0; j <= 100; ++j) {
            le[v][j] |= le[graph[v][i].first][j];
        }
    }
}

void solve() {
    ll n; cin >> n;
    vi a(n); cin >> a;
    for (ll i = 0; i < n - 1; ++i) {
        ll v, u; cin >> v >> u;
        v--, u--;
        graph[v].push_back(mp(u, a[u]));
    }
    dfs(0, a);
    ll x1 = 0, x2 = 0;
    for (ll j = 0; j <= 100; ++j) {
        x1 += le[0][j];
        x2 += re[0][j];
    }
    cout << x1 * x2;
}

int main() {
    srand(time(0));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif
    cout.precision(30);
    
    solve();
 
    return 0;
}

Compilation message

uzastopni.cpp: In function 'void dfs(long long int, std::__debug::vector<long long int>&)':
uzastopni.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i = 0; i < graph[v].size(); ++i) {
                    ~~^~~~~~~~~~~~~~~~~
uzastopni.cpp:71:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i = pos + 1; i < graph[v].size(); ++i) {
                          ~~^~~~~~~~~~~~~~~~~
uzastopni.cpp:81:14: warning: variable 'fnd' set but not used [-Wunused-but-set-variable]
         bool fnd = 0;
              ^~~

Subtask #1
120.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1024 KB Output isn't correct
2 Incorrect 6 ms 1024 KB Output isn't correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 6 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 1076 KB Output is correct
8 Incorrect 6 ms 1152 KB Output isn't correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 6 ms 1024 KB Output is correct
11 Incorrect 32 ms 17400 KB Output isn't correct
12 Incorrect 32 ms 17400 KB Output isn't correct
13 Correct 31 ms 17400 KB Output is correct
14 Correct 34 ms 21624 KB Output is correct
15 Correct 34 ms 21624 KB Output is correct
16 Correct 34 ms 21600 KB Output is correct
17 Correct 32 ms 17408 KB Output is correct
18 Correct 32 ms 17400 KB Output is correct
19 Correct 28 ms 17400 KB Output is correct
20 Correct 29 ms 17400 KB Output is correct