Submission #850676

#TimeUsernameProblemLanguageResultExecution timeMemory
850676TahirAliyevVinjete (COI22_vinjete)C++17
24 / 100
5 ms804 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long int #define oo 1e9 #define pii pair<ll, int> const int MAX = 1002; int n, m; vector<array<int, 3>> g[MAX]; pii combine(pii a, pii b){ if(a.second < b.first - 1 || b.second < a.first - 1){ return {-1, -1}; } return {min(a.first, b.first), max(a.second, b.second)}; } set<pii> s; int ans[MAX]; void dfs(int node, int p, int l, int r){ vector<pii> del; for(auto& a : s){ pii c = combine(a, {l, r}); if(c.first == -1){ ans[node] += a.second - a.first + 1; continue; } del.push_back(a); l = c.first, r = c.second; } for(auto& a : del){ s.erase(a); } ans[node] += r - l + 1; if(node != 1){ s.insert({l, r}); } for(auto to : g[node]){ if(p == to[0]) continue; dfs(to[0], node, to[1], to[2]); } s.erase({l, r}); for(auto& a : del){ s.insert(a); } } int main(){ cin >> n >> m; for(int i = 1; i < n; i++){ int a, b, l, r; cin >> a >> b >> l >> r; g[a].push_back({b, l, r}); g[b].push_back({a, l, r}); } dfs(1, 1, 0, 0); for(int i = 2; i <= n; i++){ cout << ans[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...