oj.uz

Submission #92207

# Submission time Handle Problem Language Result Execution time Memory
92207 2019-01-02T01:00:18 Z updown1 Uzastopni (COCI15_uzastopni) C++17
80 / 160
 500 ms 33792 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, MAXV)
#define ffj For(j, 0, MAXV)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int short
const int MAXN=10000, MAXV = 100;
///500,000,000
int N, joke[MAXN];
bool rng[MAXV][MAXV];
vector<int> adj[MAXN], st[MAXN], en[MAXN];

void go(int at) {
    for (int i: adj[at]) go(i);
    ffa rng[i][j] = false;
    for (int i: adj[at]) {
        for (int j: st[i]) for (int k: en[i]) if ( k < joke[at] || joke[at] < j ) rng[j][k] = true;
        st[i].clear(); en[i].clear();
    }
    rng[joke[at]][joke[at]] = true;
    For (k, 0, MAXV-1) For (i, 0, k+1) For (j, k+1, MAXV) if (rng[i][k] && rng[k+1][j]) rng[i][j] = true;
    //w<< at+1<<e; For (i, 0, 4) {For (j, 0, 4) w<< rng[i][j] << " "; w<<e;}
    bool addst[MAXN], adden[MAXN];
    ffi addst[i] = adden[i] = false;
    ffi For (j, i, MAXV) if (rng[i][j] && i <= joke[at] && joke[at] <= j) {
        if (!addst[i]) {st[at].pb(i); addst[i] = true;}
        if (!adden[j]) {en[at].pb(j); adden[j] = true;}
    }
    //w<< at+1<<e; w<< "st:"; for (int i: st[at]) w s i+1; w<<e; w<< "en:"; for (int i: en[at]) w s i+1; w<<e;
}

main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	For (i, 0, N) {cin >> joke[i]; joke[i]--;}
	For (i, 1, N) {int a, b; cin >> a >> b; a--; b--; adj[a].pb(b);}
	go(0);
	w<< st[0].size()*en[0].size()<<e;
}

Compilation message

uzastopni.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1144 KB Output is correct
2 Correct 16 ms 1144 KB Output is correct
3 Correct 18 ms 1144 KB Output is correct
4 Correct 18 ms 1144 KB Output is correct
5 Correct 21 ms 1144 KB Output is correct
6 Correct 24 ms 1656 KB Output is correct
7 Correct 24 ms 1608 KB Output is correct
8 Correct 23 ms 1656 KB Output is correct
9 Correct 23 ms 1144 KB Output is correct
10 Correct 21 ms 1272 KB Output is correct
11 Execution timed out 1060 ms 1804 KB Time limit exceeded
12 Execution timed out 1078 ms 1912 KB Time limit exceeded
13 Execution timed out 1065 ms 1836 KB Time limit exceeded
14 Runtime error 33 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 65 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 35 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Execution timed out 1086 ms 1804 KB Time limit exceeded
18 Execution timed out 1089 ms 1912 KB Time limit exceeded
19 Execution timed out 1071 ms 1620 KB Time limit exceeded
20 Execution timed out 1071 ms 1576 KB Time limit exceeded