Submission #92209

# Submission time Handle Problem Language Result Execution time Memory
92209 2019-01-02T01:17:28 Z updown1 Uzastopni (COCI15_uzastopni) C++17
80 / 160
19 ms 4344 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];
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);
    }
    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);
    }
    //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() {
      ^
# 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 Incorrect 2 ms 1016 KB Output isn't correct
4 Incorrect 2 ms 1016 KB Output isn't correct
5 Incorrect 2 ms 1020 KB Output isn't correct
6 Correct 2 ms 1016 KB Output is correct
7 Correct 2 ms 1144 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 2 ms 1016 KB Output is correct
10 Correct 2 ms 1016 KB Output is correct
11 Incorrect 10 ms 1912 KB Output isn't correct
12 Incorrect 9 ms 1912 KB Output isn't correct
13 Incorrect 11 ms 1784 KB Output isn't correct
14 Incorrect 19 ms 4344 KB Output isn't correct
15 Correct 19 ms 4216 KB Output is correct
16 Incorrect 18 ms 4344 KB Output isn't correct
17 Incorrect 9 ms 1912 KB Output isn't correct
18 Incorrect 10 ms 1832 KB Output isn't correct
19 Correct 8 ms 1784 KB Output is correct
20 Correct 8 ms 1784 KB Output is correct