Submission #251759

#	Time	Username	Problem	Language	Result	Execution time	Memory
251759		Vimmer	Uzastopni (COCI15_uzastopni)	C++14	24 / 160	11 ms	640 KiB

uzastopni

#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 / 160