Submission #1210225

#TimeUsernameProblemLanguageResultExecution timeMemory
1210225bakhtiyarnVinjete (COI22_vinjete)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e8; const int N2 = 1e5+5; vector<array<int, 3>> g[N2]; int ans[N2]; int n, M; int nxt = 1; int L[N], R[N], sg[N], lz[N]; vector<array<int, 2>> chsg; vector<array<int, 2>> chlz; unordered_map<int, int> usedsg, usedlz; void push(int u, int l, int r, int U){ if(lz[u]) { if(!usedsg[u]) usedsg[u] = 1, chsg.push_back({u, sg[u]}); sg[u] = r-l+1; } if(l != r){ if(L[u]){ if(!usedlz[L[u]]) usedlz[L[u]] = 1, chlz.push_back({L[u], lz[L[u]]}); lz[L[u]] += lz[u]; } if(R[u]){ if(!usedlz[R[u]]) usedlz[R[u]] = 1, chlz.push_back({R[u], lz[R[u]]}); lz[R[u]] += lz[u]; } } } void update(int u, int l, int r, int x, int y, int U){ push(u, l, r, U); if(y < l or x > r) return; if(x <= l and y >= r){ if(!usedlz[u]) usedlz[u] = 1, chlz.push_back({u, lz[u]}); lz[u]++; push(u, l, r, U); return; } /// int m = (l+r)/2; bool sol = true; if(y < l or x > m) sol = false; if(sol){ if(!L[u]) L[u] = ++nxt; push(u, l, r, U); update(L[u], l, m, x, y, U); } else { if(L[u]){ push(L[u], l, m, U); } } bool sag = true; if(y < m+1 or x > r) sag = false; if(sag){ if(!R[u]) R[u] = ++nxt; push(u, l, r, U); update(R[u], m+1, r, x, y, U); } else { if(R[u]){ push(R[u], m+1, r, U); } } /// if(!usedsg[u]) usedsg[u] = 1, chsg.push_back({u, sg[u]}); sg[u] = sg[L[u]] + sg[R[u]]; if(lz[u]) sg[u] = r-l+1; } void dfs(int u, int p, int li, int ri){ usedlz.clear(); usedsg.clear(); chlz.clear(); chsg.clear(); update(1, 1, M, li, ri, u); ans[u] = sg[1]; vector<array<int, 2>> chsg2 = chsg; vector<array<int, 2>> chlz2 = chlz; for(auto [to, lj, rj]: g[u]){ if(to == p) continue; dfs(to, u, lj, rj); } for(auto [node, ans]: chsg2) sg[node] = ans; for(auto [node, ans]: chlz2) lz[node] = ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> M; for(int i=1; i<n; i++){ int x, y, li, ri; cin >> x >> y >> li >> ri; g[x].push_back({y, li, ri}); g[y].push_back({x, li, ri}); } dfs(1, -1, 0, 0); for(int i=2; i<=n; i++) cout << ans[i] << '\n'; }

Compilation message (stderr)

/tmp/ccLziVLw.o: in function `__tcf_0':
Main.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `g' defined in .bss section in /tmp/ccLziVLw.o
/tmp/ccLziVLw.o: in function `push(long long, long long, long long, long long)':
Main.cpp:(.text+0x9a): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccLziVLw.o
/tmp/ccLziVLw.o: in function `update(long long, long long, long long, long long, long long, long long)':
Main.cpp:(.text+0x368): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccLziVLw.o
Main.cpp:(.text+0x3dc): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccLziVLw.o
Main.cpp:(.text+0x453): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccLziVLw.o
Main.cpp:(.text+0x484): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccLziVLw.o
/tmp/ccLziVLw.o: in function `dfs(long long, long long, long long, long long)':
Main.cpp:(.text+0x7a1): relocation truncated to fit: R_X86_64_PC32 against symbol `M' defined in .bss section in /tmp/ccLziVLw.o
Main.cpp:(.text+0x7c7): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/ccLziVLw.o
Main.cpp:(.text+0x8e6): relocation truncated to fit: R_X86_64_PC32 against symbol `g' defined in .bss section in /tmp/ccLziVLw.o
/tmp/ccLziVLw.o: in function `main':
Main.cpp:(.text.startup+0x11): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
Main.cpp:(.text.startup+0x33): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status