oj.uz

답안 #92208

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92208 2019-01-02T01:12:01 Z updown1 Uzastopni (COCI15_uzastopni) C++17
80 / 160
 500 ms 3688 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], addst[MAXN], adden[MAXN];
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;}
    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:41:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
80.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1016 KB Output is correct
2 Correct 16 ms 1144 KB Output is correct
3 Correct 18 ms 1016 KB Output is correct
4 Correct 18 ms 1144 KB Output is correct
5 Correct 24 ms 1144 KB Output is correct
6 Correct 23 ms 1144 KB Output is correct
7 Correct 22 ms 888 KB Output is correct
8 Correct 22 ms 1016 KB Output is correct
9 Correct 23 ms 1116 KB Output is correct
10 Correct 22 ms 1016 KB Output is correct
11 Execution timed out 1071 ms 1616 KB Time limit exceeded
12 Execution timed out 1077 ms 1628 KB Time limit exceeded
13 Execution timed out 1078 ms 1740 KB Time limit exceeded
14 Execution timed out 1086 ms 3456 KB Time limit exceeded
15 Execution timed out 1072 ms 3572 KB Time limit exceeded
16 Execution timed out 1066 ms 3688 KB Time limit exceeded
17 Execution timed out 1075 ms 1784 KB Time limit exceeded
18 Execution timed out 1071 ms 1656 KB Time limit exceeded
19 Execution timed out 1070 ms 1660 KB Time limit exceeded
20 Execution timed out 1081 ms 1656 KB Time limit exceeded