제출 #970695

#제출 시각아이디문제언어결과실행 시간메모리
970695PentagonHarbingers (CEOI09_harbingers)C++17
컴파일 에러
0 ms0 KiB
#pragma GCC optimize(3) #pragma GCC optimize("Ofast,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt") #include"bits/stdc++.h" using namespace std; #define nl '\n' #define sp ' ' #define dbg(i) cerr<<#i<<sp<<i<<endl #define dbgs(...) fprintf(stderr, __VA_ARGS__) #define all(v) (v).begin(), (v).end() using ll = long long; // dont use below with atcoder header or tight constrain // #define int ll using pii = pair<int,int>; int cur_tc; std::mt19937_64 gen(time(NULL)); ll randint(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); } /*Solution https://acmicpc.net/problem/3319 1. 문제부터 정확히 읽는다. 2. 사고 전환을 빠르게 한다. 3. 한줄 한줄 정신 차리고 작성한다. */ constexpr int N = 1e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7, LOOP = 3e5; constexpr ll linf = (ll)4e18 + 7; /* rollback Line container for dynamic CHT that can be Rollbacked. (Persistent) y = kx + m qry: gives minimum value for given x, Lower hull find bool operator< (const Line& o) to change minimum / maximum properties. for minimum: k > o.k, x->m < y->m for maximum: k < o.k, x->m > y->m for doubles, change all (ll -> double), (inf -> 1/.0), (div(a,b) = a/b) reference: https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LineContainer.h */ struct Line{ mutable ll k, m, p; bool operator<(const Line& o) const{return k!=o.k?k>o.k:m<o.m;} // chg here bool operator<(ll x) const {return p < x;} }; struct LineContainer : multiset<Line, less<>> { static const ll inf = LLONG_MAX; ll div(ll a, ll b){ // floored division return a / b - ((a ^ b) < 0 && a % b); } bool apply(iterator x, iterator y){ if(y == end()){ x->p = inf; return false; } if(x->k == y->k) x->p = (*x<*y?inf:-inf); else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } vector<int> info; vector<Line> S; bool add(ll k, ll m){ auto z = insert({k, m, -inf}), y = z++, x = y; auto it = x; vector<Line> v; while(apply(y, z)) v.push_back(*z), z = erase(z); if(x != begin() && apply(--x, y)){ apply(x, y = erase(y)); assert(v.size() == 0); info.push_back(0); return false; } reverse(v.begin(), v.end()); while((y=x) != begin() && (--x)->p >= y->p) v.push_back(*y), apply(x, erase(y)); reverse(v.begin(), v.end()); assert(it != end()); v.push_back(*it); S.insert(S.end(), v.begin(), v.end()); info.push_back(v.size()); return true; } void print_it(iterator it){dbgs("%dth %lld %lld %lld\n",(int)distance(begin(),it), it->k, it->m, it->p);} void print(){ dbg(size()); for(auto it = begin(); it != end(); it++) print_it(it); } void rollback(){ // print(); assert(!info.empty()); auto c = info.back(); info.pop_back(); if(c == 0) return; assert(c <= (int)S.size()); auto l = S.back(); S.pop_back(); --c; auto it = lower_bound(l); assert(it != end() && it->k == l.k && it->m == l.m); it = erase(it); if(c==0){ if(it != begin()) apply(prev(it), it); return; } if(it != begin()) --it; auto y = it; for(int i=1;i<=c;i++) y = insert(y, S[S.size()-i]); S.resize(S.size()-c); if(it == next(y)) it = begin(); for(auto x = y++; ;--x, --y){// note that x's initial iterator is valid apply(x, y); if(x == it) break; } } ll qry(ll x){ assert(!empty()); auto l = lower_bound(x); assert(l != end()); return l->k * x + l->m; } }; LineContainer lc; vector<pii> g[N]; int par[N], S[N], V[N]; ll dep[N], dp[N]; void dfs(int x){ if(x != 1) dp[x] = S[x] + dep[x] * V[x] + lc.qry(V[x]); lc.add(-dep[x], dp[x]); for(auto [nx, d]:g[x]) if(nx != par[x]){ dep[nx] = dep[x] + d; par[nx] = x; dfs(nx); } lc.rollback(); } void solve(){ int n; cin>>n; for(int i=0;i<n-1;i++){ int a, b, d; cin>>a>>b>>d; g[a].push_back(pii(b,d)); g[b].push_back(pii(a,d)); } for(int i=2;i<=n;i++) cin>>S[i]>>V[i]; lc.S.reserve(n); lc.info.reserve(n); dfs(1); for(int i=2;i<=n;i++) cout<<dp[i]<<sp; cout<<nl; } signed main(){ cin.tie(0)->sync_with_stdio(0); // cout<<fixed<<setprecision(15); int tc = 1; // cin >> tc; for(cur_tc=1;cur_tc<=tc;++cur_tc) solve(); return 0; }v

컴파일 시 표준 에러 (stderr) 메시지

harbingers.cpp:145:2: error: 'v' does not name a type
  145 | }v
      |  ^