Submission #695332

#	Time	Username	Problem	Language	Result	Execution time	Memory
695332		Nhoksocqt1	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	84 ms	17968 KiB

uzastopni

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int readInt() {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while(true) {
		if(ch == '-') break;
		if(ch >= '0' && ch <= '9') break;
		ch = getchar();
	}

	if(ch == '-') minus = true; else result = ch - '0';
	while(true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result * 10 + (ch - '0');
	}

	if(minus)
		return -result;
	else
		return result;
}

const int MAXN = 10004;
const int MAXM = 100;

vector<int> adj[MAXN];
int val[MAXN], numNode;
bitset<MAXM + 2> dp[MAXN][MAXM + 2];

void dfs(int u, int p) {
    dp[u][val[u]][val[u]] = 1;
    sort(adj[u].begin(), adj[u].end(), [](const int &a, const int &b) {
        return (val[a] < val[b]);
    });

    for (int it = 0; it < int(adj[u].size()); ++it) {
        int v(adj[u][it]);
        if(v != p && val[v] > val[u]) {
            dfs(v, u);
            for (int i = 1; i <= MAXM; ++i) {
                for (int j = 1; j < i; ++j) {
                    if(dp[u][j][i - 1])
                        dp[u][j] |= dp[v][i];

                    if(dp[v][j][i - 1])
                        dp[u][j] |= dp[u][i];
                }
            }
        }
    }

    reverse(adj[u].begin(), adj[u].end());
    for (int it = 0; it < int(adj[u].size()); ++it) {
        int v(adj[u][it]);
        if(v != p && val[v] < val[u]) {
            dfs(v, u);
            for (int i = 1; i <= MAXM; ++i) {
                for (int j = 1; j < i; ++j) {
                    if(dp[u][j][i - 1])
                        dp[u][j] |= dp[v][i];

                    if(dp[v][j][i - 1])
                        dp[u][j] |= dp[u][i];
                }
            }
        }
    }
}

void process() {
    cin >> numNode;
    for (int i = 1; i <= numNode; ++i)
        cin >> val[i];

    for (int i = 1; i < numNode; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    int res(0);
    for (int i = 1; i <= MAXM; ++i)
        res += dp[1][i].count();

    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("uzastopni.inp", "r", stdin);
//    freopen("uzastopni.out", "w", stdout);

    process();
    return 0;
}

Compilation message (stderr)

uzastopni.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
uzastopni.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 160 / 160