oj.uz

Submission #251759

# Submission time Handle Problem Language Result Execution time Memory
251759 2020-07-22T09:30:50 Z Vimmer Uzastopni (COCI15_uzastopni) C++14
24 / 160
 11 ms 640 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 10010
#define M ll(10007)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <int, 3> a3;
typedef array <int, 4> a4;
typedef pair <int, int> pt;
//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int n, val[105], ans, from[N], a[N];

set <int> se;

vector <int> g[N];

bool mk[N], bad;

void dfs_rev(int v)
{
    while (1)
    {
        if (se.find(v) == se.end()) {bad = 1; return;}

        if (mk[v] || v == 1) return;

        int nxt = from[v];

        if (abs(a[nxt] - a[v]) != 1) {bad = 1; return;}

        mk[v] = 1;

        v = nxt;
    }
}

int main()
{
    //freopen("mining.in", "r", stdin); freopen("mining.out", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    set <int> st; st.clear();

    for (int i = 1; i <= n; i++) {cin >> a[i]; st.insert(a[i]); val[a[i]] = i;}

    if (sz(st) != n) {cout << 0 << endl; exit(0);}

    for (int i = 1; i < n; i++)
    {
        int x, y;

        cin >> x >> y;

        g[x].pb(y);

        from[y] = x;
    }

    for (int l = 1; l <= 100; l++)
        for (int r = l; r <= 100; r++)
            if (l <= a[1] && a[1] <= r)
            {
                bad = 0;

                se.clear();

                for (int i = l; i <= r; i++) if (val[i] == 0) {bad = 1; break;} else se.insert(val[i]);

                if (bad) continue;

                memset(mk, 0, sizeof(mk));

                for (int i = l; i <= r && !bad; i++) dfs_rev(val[i]);

                if (!bad) ans++;
            }

    cout << ans << endl;
}

Subtask #1
24.0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 512 KB Output isn't correct
2 Incorrect 0 ms 512 KB Output isn't correct
3 Incorrect 0 ms 512 KB Output isn't correct
4 Incorrect 1 ms 512 KB Output isn't correct
5 Incorrect 0 ms 512 KB Output isn't correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 11 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Incorrect 0 ms 512 KB Output isn't correct
10 Incorrect 0 ms 640 KB Output isn't correct
11 Incorrect 2 ms 640 KB Output isn't correct
12 Incorrect 1 ms 640 KB Output isn't correct
13 Incorrect 1 ms 640 KB Output isn't correct
14 Incorrect 2 ms 640 KB Output isn't correct
15 Incorrect 2 ms 640 KB Output isn't correct
16 Incorrect 1 ms 640 KB Output isn't correct
17 Incorrect 1 ms 640 KB Output isn't correct
18 Incorrect 1 ms 640 KB Output isn't correct
19 Incorrect 2 ms 640 KB Output isn't correct
20 Incorrect 2 ms 640 KB Output isn't correct