oj.uz

Submission #92210

# Submission time Handle Problem Language Result Execution time Memory
92210 2019-01-02T01:21:11 Z updown1 Uzastopni (COCI15_uzastopni) C++17
160 / 160
 20 ms 5624 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 ll
const int MAXN=10000, MAXV = 100;
///500,000,000
int N, joke[MAXN];
vector<int> adj[MAXN], st[MAXN], en[MAXN], dirfor[MAXV], dirbck[MAXV];
queue<int> nxt;
bool vis[MAXV];

void go(int at) {
    for (int i: adj[at]) go(i);
    ffi dirfor[i].clear(), dirbck[i].clear();
    for (int i: adj[at]) for (int j: st[i]) for (int k: en[i]) if ( k < joke[at] || joke[at] < j ) dirfor[j].pb(k), dirbck[k].pb(j);
    ffi vis[i] = false;
    nxt.push(joke[at]);
    vis[joke[at]] = true;
    while (!nxt.empty()) {
        int x = nxt.front(); nxt.pop();
        en[at].pb(x);
        if (x == MAXV-1) continue;
        for (int i: dirfor[x+1]) if (!vis[i]) {nxt.push(i); vis[i] = true;}
    }
    ffi vis[i] = false;
    nxt.push(joke[at]);
    vis[joke[at]] = true;
    while (!nxt.empty()) {
        int x = nxt.front(); nxt.pop();
        st[at].pb(x);
        if (x == 0) continue;
        for (int i: dirbck[x-1]) if (!vis[i]) {nxt.push(i); vis[i] = 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:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 2 ms 1016 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 2 ms 1016 KB Output is correct
7 Correct 2 ms 1144 KB Output is correct
8 Correct 2 ms 1144 KB Output is correct
9 Correct 2 ms 1016 KB Output is correct
10 Correct 2 ms 1016 KB Output is correct
11 Correct 10 ms 1912 KB Output is correct
12 Correct 10 ms 1912 KB Output is correct
13 Correct 9 ms 1884 KB Output is correct
14 Correct 20 ms 5624 KB Output is correct
15 Correct 20 ms 5624 KB Output is correct
16 Correct 20 ms 5624 KB Output is correct
17 Correct 12 ms 1912 KB Output is correct
18 Correct 10 ms 1912 KB Output is correct
19 Correct 8 ms 1756 KB Output is correct
20 Correct 8 ms 1784 KB Output is correct