Submission #695332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
695332	2023-02-05T02:59:32 Z	Nhoksocqt1	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	84 ms	17968 KB

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

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.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	724 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	2 ms	724 KB	Output is correct
10	Correct	1 ms	696 KB	Output is correct
11	Correct	44 ms	15512 KB	Output is correct
12	Correct	18 ms	8336 KB	Output is correct
13	Correct	23 ms	10000 KB	Output is correct
14	Correct	84 ms	17904 KB	Output is correct
15	Correct	70 ms	17968 KB	Output is correct
16	Correct	72 ms	17912 KB	Output is correct
17	Correct	10 ms	4308 KB	Output is correct
18	Correct	28 ms	11248 KB	Output is correct
19	Correct	4 ms	1236 KB	Output is correct
20	Correct	4 ms	1236 KB	Output is correct