# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
675328 | vjudge1 | Uzastopni (COCI15_uzastopni) | C++17 | 78 ms | 24388 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int, int>
using namespace std;
const int mxN = 1e4 + 5;
const int BIT = 1e2 + 5;
int numNode, a[mxN];
vector <int> adj[mxN], q[BIT];
vector <pii> s[mxN];
bitset <BIT> bit[mxN][BIT];
void Shiba_Read()
{
cin >> numNode;
for (int i = 1; i <= numNode; ++i)
cin >> a[i];
for (int i = 2; i <= numNode; ++i)
{
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void Shiba_Dfs(int u, int p)
{
for (int v : adj[u])
{
if (v != p)
Shiba_Dfs(v, u);
}
for (int i = 0; i < BIT; ++i) q[i].clear();
for (int v : adj[u])
{
if (v != p)
{
for (pii it : s[v])
q[it.fi].push_back(it.se);
}
}
for (int i = BIT - 1; i >= 1; --i)
{
if (i == a[u])
{
bit[u][i] |= bit[u][i + 1];
bit[u][i].set(i);
}
else
{
for (int j : q[i])
{
if (i > a[u] || j < a[u])
{
bit[u][i] |= bit[u][j + 1];
bit[u][i].set(j);
}
}
}
for (int j = BIT - 1; j >= i; --j)
{
if (bit[u][i].test(j) && a[u] >= i && a[u] <= j)
s[u].push_back(make_pair(i, j));
}
}
}
void Shiba_Process()
{
Shiba_Dfs(1, 0);
cout << s[1].size();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Shiba_Read();
Shiba_Process();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |