Submission #536024

#TimeUsernameProblemLanguageResultExecution timeMemory
536024akhan42Uzastopni (COCI15_uzastopni)C++17
160 / 160
24 ms2856 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define forn(i, n) for(int i = 0; i < n; ++i) #define forbn(i, b, n) for(int i = b; i < n; ++i) #define sz(v) (int)v.size() #define pb push_back #define mp make_pair #define eb emplace_back #define all(v) v.begin(), v.end() #define min3(a, b, c) min(a, min(b, c)) #define lc v << 1 #define rc (v << 1) + 1 typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef long long ll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; template <class T> inline void mineq(T &a, T b) { a = min(a, b); } template <class T> inline void maxeq(T &a, T b) { a = max(a, b); } const int MX = 10 * 1000; vi gr[MX]; int jokes[MX]; bitset<100> gl_gr[100]; vi att; void dfs2(int node) { att[node] = true; for(int nb = gl_gr[node]._Find_first(); nb < sz(gl_gr[node]); nb = gl_gr[node]._Find_next(nb)) { if(!att[nb]) dfs2(nb); } } vii dfs(int node = 0) { vii edges; for(int nb: gr[node]) { vii links = dfs(nb); for(ii p: links) { if(jokes[node] < min(p.F, p.S)) edges.eb(p.F - 1, p.S); else if(jokes[node] > max(p.F, p.S)) edges.eb(p.S + 1, p.F); } } att.assign(100, false); forn(i, 100) gl_gr[i].reset(); for(ii p: edges) gl_gr[p.F][p.S] = 1; dfs2(jokes[node]); vi left, right; forbn(l, 0, jokes[node] + 1) if(att[l]) left.pb(l); forbn(r, jokes[node], 100) if(att[r]) right.pb(r); edges.clear(); for(int l: left) for(int r: right) edges.eb(l, r); return edges; } void solve() { int n; cin >> n; forn(i, n) { cin >> jokes[i]; jokes[i]--; } forn(_, n - 1) { int a, b; cin >> a >> b; a--; b--; gr[a].pb(b); } vii links = dfs(0); cout << sz(links); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // freopen("triangles.in", "r", stdin); // freopen("triangles.out", "w", stdout); int t = 1; // cin >> t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...