Submission #1188077

#TimeUsernameProblemLanguageResultExecution timeMemory
1188077AliyyiakbarVinjete (COI22_vinjete)C++20
24 / 100
253 ms589824 KiB
#include <bits/stdc++.h> // author: vusal #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int oo = 1e18 + 9; const int sz = 5e4+7; const int MOD = 1e9+7; int n, m; vector<array<int,3>>g[sz]; vector<pair<int,int>>v[sz]; bitset<sz> vis; int getsz(vector<pair<int,int>>&v) { if(v.empty()) return 0; sort(v.begin(), v.end()); int cl = v[0].first; // left int cr = v[0].second; // right int sum = 0; for(int i = 1; i < v.size(); i++) { int nl = v[i].first, nr = v[i].second; if(nl > cr) { sum += (cr - cl + 1); cr = nr; cl = nl; } else { cr = max(cr, nr); } } sum += (cr - cl + 1); return sum; } void solve() { cin >> n >> m; for(int i = 0; i < n -1; i++) { int u, v, l, r; cin >> u >> v >> l >> r; g[u].push_back({v, l, r}); g[v].push_back({u, l, r}); } queue<int>q; q.push(1); vis[1] = 1; while(!q.empty()) { int u = q.front();q.pop(); for(auto &[to, l, r] : g[u]) { if(vis[to] == 1) continue; v[to] = v[u]; v[to].push_back(make_pair(l, r)); q.push(to); vis[to] = 1; } } for(int i = 2; i <= n; i++) { cout << getsz(v[i]) << endl; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tc = 1; // cin >> tc; for(int i = 1; i <= tc; i++) { //cout << "Case " << i << ":"; solve(); } return 0; }
#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...