| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1039767 |
2024-07-31T08:38:11 Z |
변재우(#10994) |
Sprinklers (CEOI24_sprinklers) |
C++17 |
|
0 ms |
0 KB |
// #include <bits/stdc++.h>
// #define int long long
// using namespace std;
// const int N=70010, S=(1<<17);
// int n, k, siz[N], dep[N], par[17][N], up[N], ans[N];
// bool is_cent[N];
// vector<pair<int, int>> adj[N];
// class LazySeg {
// public:
// LazySeg(vector<int> tot) {
// X=tot.size();
// S=(1<<(32-__builtin_clz(X-1)));
// Tree.resize(2*S), Lazy1.resize(2*S), Lazy2.resize(2*S);
// p=1;
// R.push_back({});
// for(int i=1; i<=X; i++) {
// Add(1, 1, S, i, i, tot[i-1]);
// }
// R.pop_back();
// }
// int Add(int x) {
// int ret=0;
// R.push_back({});
// Add(1, 1, S, 1, X, x);
// int tmp=0;
// for(int s=p, e=X; s<=e; ) {
// int m=(s+e)/2;
// if(Query(1, 1, S, m)>k) tmp=m, e=m-1;
// else s=m+1;
// }
// if(!tmp) {
// int tmp2=0;
// for(int s=1, e=p-1; s<=e; ) {
// int m=(s+e)/2;
// if(Query(1, 1, S, m)>k) tmp=m, e=m-1;
// else s=m+1;
// }
// if(tmp2) Cover(1, 1, S, tmp2, p-1), p=tmp2;
// }
// else if(tmp>p) Cover(1, 1, S, tmp, X), ret=X-tmp+1, p=tmp;
// else {
// Cover(1, 1, S, 1, X), ret=X;
// p=1;
// }
// return ret;
// }
// void RollBack() {
// for(int i=R.back().size()-1; i>=0; i--) {
// int k=R.back()[i].first, v=R.back()[i].second;
// if(k<=2*S) Tree[k]=v;
// else if(k<=4*S) Lazy1[k-2*S]=v;
// else Lazy2[k-4*S]=v;
// }
// R.pop_back();
// }
// private:
// int S, X, p;
// vector<int> Tree, Lazy1, Lazy2;
// vector<vector<pair<int, int>>> R;
// void Propagate(int node, int s, int e) {
// if(s==e) {
// if(Lazy1[node]) R.back().push_back({node, Tree[node]}), Tree[node]=0;
// if(Lazy2[node]) R.back().push_back({node, Tree[node]}), Tree[node]+=Lazy2[node];
// }
// else {
// if(Lazy1[node]) {
// R.back().push_back({2*node+4*S, Lazy2[2*node]});
// R.back().push_back({2*node+1+4*S, Lazy2[2*node]});
// R.back().push_back({2*node+2*S, Lazy2[2*node]});
// R.back().push_back({2*node+1+2*S, Lazy2[2*node]});
// Lazy2[2*node]=Lazy2[2*node+1]=0;
// Lazy1[2*node]=Lazy1[2*node+1]=1;
// }
// if(Lazy2[node]) {
// R.back().push_back({2*node+4*S, Lazy2[2*node]});
// R.back().push_back({2*node+1+4*S, Lazy2[2*node+1]});
// Lazy2[2*node]+=Lazy2[node];
// Lazy2[2*node+1]+=Lazy2[node];
// }
// }
// R.back().push_back({node+2*S, Lazy1[node]});
// R.back().push_back({node+4*S, Lazy2[node]});
// Lazy1[node]=Lazy2[node]=0;
// return;
// }
// void Add(int node, int s, int e, int l, int r, int v) {
// Propagate(node, s, e);
// if(s>r || l>e) return;
// if(l<=s && e<=r) {
// R.back().push_back({node+4*S, Lazy2[node]});
// Lazy2[node]=v;
// Propagate(node, s, e);
// return;
// }
// int lch=2*node, rch=lch+1, m=(s+e)/2;
// Add(lch, s, m, l, r, v), Add(rch, m+1, e, l, r, v);
// }
// void Cover(int node, int s, int e, int l, int r) {
// Propagate(node, s, e);
// if(s>r || l>e) return;
// if(l<=s && e<=r) {
// R.back().push_back({node+2*S, Lazy1[node]});
// Lazy1[node]=1;
// Propagate(node, s, e);
// return;
// }
// int lch=2*node, rch=lch+1, m=(s+e)/2;
// Cover(lch, s, m, l, r), Cover(rch, m+1, e, l, r);
// }
// int Query(int node, int s, int e, int k) {
// Propagate(node, s, e);
// if(s==e) return Tree[node];
// int lch=2*node, rch=lch+1, m=(s+e)/2;
// if(k<=m) return Query(lch, s, m, k);
// else return Query(rch, m+1, e, k);
// }
// };
// int dfs_size(int curr, int prev) {
// siz[curr]=1;
// for(auto [next, w]:adj[curr]) if(next!=prev && !is_cent[next]) siz[curr]+=dfs_size(next, curr);
// return siz[curr];
// }
// int dfs_cent(int curr, int prev, int s) {
// for(auto [next, w]:adj[curr]) if(next!=prev && !is_cent[next] && siz[next]>=s/2) return dfs_cent(next, curr, s);
// return curr;
// }
// void dfs_pre(int curr, int prev) {
// up[curr]=0, siz[curr]=1;
// for(int i=1; i<=16; i++) par[i][curr]=par[i-1][par[i-1][curr]];
// for(auto [next, w]:adj[curr]) if(next!=prev && !is_cent[next])
// dep[next]=dep[curr]+1, par[0][next]=curr, dfs_pre(next, curr), siz[curr]+=siz[next];
// }
// void dfs_up(int curr, int prev, int root, vector<int> &tmp, int wt) {
// for(auto [next, w]:adj[curr]) if(next!=prev && !is_cent[next]) dfs_up(next, curr, root, tmp, wt);
// up[curr]++;
// cout<<"up["<<curr<<"]: "<<up[curr]<<"\n";
// cout<<"ans["<<curr<<"]: "<<ans[curr]<<"\n";
// cout<<"wt: "<<wt<<"\n";
// if(dep[curr]-dep[root]<k) {
// for(int i=1; i<=up[curr]; i++) tmp.push_back(dep[curr]-dep[root]);
// }
// else {
// int p=curr;
// for(int i=16; i>=0; i--) if(par[i][p] && dep[par[i][p]] && dep[curr]-dep[par[i][p]]<=k) p=par[i][p];
// up[par[0][p]]+=up[curr], ans[p]+=up[curr]*wt;
// }
// }
// void dfs_down(int curr, int prev, LazySeg &tree, int sign) {
// for(auto [next, w]:adj[curr]) if(next!=prev && !is_cent[next]) {
// ans[curr]+=tree.Add(w)*siz[next]*sign;
// dfs_down(next, curr, tree, sign);
// tree.RollBack();
// }
// }
// void dfs_fromcent(int curr, int prev, int v) {
// for(auto [next, w]:adj[curr]) if(next!=prev && !is_cent[next]) {
// if(v+w>k) ans[curr]+=siz[next], dfs_fromcent(next, curr, w);
// else dfs_fromcent(next, curr, v+w);
// }
// }
// void f(int st) {
// int sz=dfs_size(st, 0);
// int cent=dfs_cent(st, 0, sz);
// cout<<"Cent: "<<cent<<"\n";
// dep[cent]=0, par[0][cent]=0, is_cent[cent]=true;
// dfs_pre(cent, 0);
// dfs_fromcent(cent, 0, 0);
// vector<vector<int>> val;
// vector<int> tot;
// for(auto [next, w]:adj[cent]) if(!is_cent[next]) {
// vector<int> tmp, tmp2;
// dfs_up(next, cent, next, tmp, siz[cent]-siz[next]);
// cout<<"tmp "<<next<<": ";
// for(int v:tmp) cout<<v<<" "; cout<<"\n";
// for(int i:tmp) {
// if(i+w>k) ans[next]+=siz[cent]-siz[next], tmp2.push_back(w);
// else tmp2.push_back(i+w);
// }
// sort(tmp2.begin(), tmp2.end());
// val.push_back(tmp2);
// for(int i:tmp2) tot.push_back(i);
// }
// cout<<"After up pass\n";
// for(int i=1; i<=n; i++) cout<<ans[i]<<" "; cout<<"\n";
// sort(tot.begin(), tot.end());
// LazySeg tree(tot);
// dfs_down(cent, 0, tree, 1);
// cout<<"After down pass including same subtree\n";
// for(int i=1; i<=n; i++) cout<<ans[i]<<" "; cout<<"\n";
// int p=0;
// for(auto [next, w]:adj[cent]) if(!is_cent[next]) {
// LazySeg tree2(val[p++]);
// ans[cent]-=tree.Add(w)*siz[next];
// dfs_down(next, cent, tree, -1);
// }
// cout<<"After all path passing "<<cent<<"\n";
// for(int i=1; i<=n; i++) cout<<ans[i]<<" "; cout<<"\n";
// for(auto [next, w]:adj[cent]) if(!is_cent[next]) f(next);
// }
// signed main() {
// ios_base::sync_with_stdio(0), cin.tie(0);
// cin>>n>>k;
// for(int i=1; i<n; i++) {
// int u, v, w; cin>>u>>v>>w;
// u++, v++;
// adj[u].push_back({v, w}), adj[v].push_back({u, w});
// }
// f(1);
// for(int i=1; i<=n; i++) cout<<ans[i]<<"\n";
// return 0;
// }
Compilation message
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status
