oj.uz

Submission #128395

# Submission time Handle Problem Language Result Execution time Memory
128395 2019-07-10T21:24:56 Z Gustav Uzastopni (COCI15_uzastopni) C++14
64 / 160
 500 ms 11580 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 1000000007;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())


int n;
vvi adj;
vi k;

vvi adj2;
vi visited;

void dfs2(int node, bool back){
    if(visited[node]) return;
    visited[node] = 1;
    for(int x : adj2[node]){
        dfs2(x, back);
    }
    if(!back && node >= 60000) dfs2(node-20000+1, back);
    if(back && node >= 40000 && node < 60000) dfs2(node+20000-1, back);
}

pair<vi, vi> dfs(int node, int par){
    vector<pair<vi, vi>> results;
    for(int x : adj[node]){
        if(x == par) continue;
        results.push_back(dfs(x, node));
    }
    adj2 = vvi(100000);
    visited = vi(100000);
    for(int i = 0; i < sz(results); i++){
        for(int x : results[i].first){
            adj2[x+40000].push_back(i);
            adj2[i+20000].push_back(x+40000);
        }
        for(int x : results[i].second){
            adj2[x+60000].push_back(i+20000);
            adj2[i].push_back(x+60000);
        }
    }
    dfs2(60000 + k[node], false);
    dfs2(40000 + k[node], true);
    vi start, end;
    for(int i = 0; i <= k[node]; i++){
        if(visited[40000+i]) start.push_back(i);
    }
    for(int i = k[node]; i < 100; i++){
        if(visited[60000+i]) end.push_back(i);
    }
    return {start, end};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    k = vi(n);
    adj = vvi(n);
    for(int i = 0; i < n; i++) {
        cin >> k[i];
        k[i]--;
    }
    for(int i = 0; i < n-1; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    pair<vi, vi> p = dfs(0, -1);
    cout << sz(p.first)*sz(p.second) << endl;
}

Subtask #1
64.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6416 KB Output is correct
2 Correct 30 ms 6156 KB Output is correct
3 Correct 33 ms 6256 KB Output is correct
4 Incorrect 32 ms 6152 KB Output isn't correct
5 Incorrect 39 ms 6284 KB Output isn't correct
6 Correct 38 ms 6284 KB Output is correct
7 Correct 38 ms 5900 KB Output is correct
8 Correct 38 ms 6280 KB Output is correct
9 Correct 41 ms 8200 KB Output is correct
10 Correct 41 ms 8204 KB Output is correct
11 Execution timed out 1067 ms 8912 KB Time limit exceeded
12 Execution timed out 1074 ms 8972 KB Time limit exceeded
13 Execution timed out 1091 ms 8980 KB Time limit exceeded
14 Execution timed out 1089 ms 11524 KB Time limit exceeded
15 Execution timed out 1079 ms 11580 KB Time limit exceeded
16 Execution timed out 1058 ms 11472 KB Time limit exceeded
17 Execution timed out 1078 ms 8980 KB Time limit exceeded
18 Execution timed out 1081 ms 8920 KB Time limit exceeded
19 Execution timed out 1086 ms 6932 KB Time limit exceeded
20 Execution timed out 1083 ms 6936 KB Time limit exceeded