QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#150533 | #6660. 택시 여행 | penguinman | 0 | 292ms | 51956kb | C++17 | 6.3kb | 2023-08-25 20:09:25 | 2023-08-25 20:09:26 |
Judging History
answer
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
constexpr ll inf = (1ll<<60);
std::vector<long long> travel(std::vector<long long> A,
std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
ll N = A.size();
vii edge(N), weight(N), d_edge(N);
rep(i,0,N-1){
edge[U[i]].pb(V[i]);
edge[V[i]].pb(U[i]);
weight[U[i]].pb(W[i]);
weight[V[i]].pb(W[i]);
}
vi dist(N, -1), par(N), hld_dist(N);
{
std::queue<ll> que;
vector<bool> visited(N);
dist[0] = 0;
que.push(0);
while(!que.empty()){
ll now = que.front(); que.pop();
rep(i,0,edge[now].size()){
ll next = edge[now][i];
if(dist[next] != -1) continue;
dist[next] = dist[now]+weight[now][i];
que.push(next);
par[next] = now;
d_edge[now].pb(next);
hld_dist[next] = hld_dist[now]+1;
}
}
}
vi c_par(N,-1);
vector<bool> dead(N);
vi subtree(N);
std::function<void(ll)> calc_subtree = [&](ll now){
subtree[now] = 1;
for(auto next: d_edge[now]){
if(dead[next]) continue;
calc_subtree(next);
subtree[now] += subtree[next];
}
};
// hld
vi hld_par(N);
std::function<void(ll)> heavy_light_decomposition = [&](ll now){
rep(i,1,d_edge[now].size()){
if(subtree[edge[now][0]] < subtree[edge[now][i]]) std::swap(edge[now][i], edge[now][0]);
}
rep(i,0,d_edge[now].size()){
ll next = d_edge[now][i];
if(i) hld_par[next] = next;
else hld_par[next] = hld_par[now];
heavy_light_decomposition(next);
}
};
auto LCA = [&](ll l, ll r){
while(true){
if(hld_dist[l] < hld_dist[r]) std::swap(l,r);
if(hld_par[l] == hld_par[r]){
return r;
}
if(l == hld_par[l]) l = par[l];
else l = hld_par[l];
}
};
auto distance = [&](ll l, ll r){
return dist[l]+dist[r]-2*dist[LCA(l,r)];
};
calc_subtree(0);
heavy_light_decomposition(0);
// centroid tree
std::function<ll(ll, ll)> find_centroid = [&](ll root, ll now){
ll max = subtree[root]-subtree[now];
for(auto next: d_edge[now]){
if(dead[next]) continue;
ll c = find_centroid(root, next);
if(c != -1) return c;
max = std::max(max, subtree[next]);
}
if(max*2 <= subtree[root]) return now;
return ll(-1);
};
std::function<void(ll,ll)> centroid_coloring = [&](ll centroid, ll now){
if(now != centroid) c_par[now] = centroid;
for(auto next: d_edge[now]){
if(dead[next]) continue;
centroid_coloring(centroid, next);
}
};
std::function<void(ll)> dfs_centroid_decomposition = [&](ll root){
if(dead[root]) return;
calc_subtree(root);
if(subtree[root] == 1) return;
ll c = find_centroid(root,root);
centroid_coloring(c, root);
dead[c] = true;
for(auto next: d_edge[c]){
dfs_centroid_decomposition(next);
}
dfs_centroid_decomposition(root);
};
dfs_centroid_decomposition(0);
vector<pii> data(N);
rep(i,0,N) data[i] = mp(B[i], i);
sort(all(data));
reverse(all(data));
vector<vector<pii>> lines(N);
// m について判定
// is_need : true → m は必要
auto is_need = [&](pii l, pii m, pii r){
return ((r.second-m.second)*(m.first-l.first) < (m.second-l.second)*(r.first-m.first));
};
auto add_line = [&](ll idx, pii l){
if(!lines[idx].empty() && lines[idx].back().first == l.first){
ll n = lines[idx].size();
if(lines[idx][n-1].second <= l.second) return;
lines[idx].pop_back();
}
while(lines[idx].size() > 1){
ll n = lines[idx].size();
if(!is_need(lines[idx][n-2], lines[idx][n-1], l)) lines[idx].pop_back();
else break;
}
lines[idx].pb(l);
};
auto value = [&](pii f, ll x){
return f.first*x+f.second;
};
auto calc = [&](ll idx, ll x){
if(lines[idx].empty()) return inf;
/*{
ll min = inf;
for(auto el: lines[idx]){
min = std::min(min, value(el, x));
cout << value(el, x) << " ";
}
cout << endl;
return min;
}*/
ll left = 0, right = lines[idx].size();
while(left+1 < right){
ll mid = (left+right)/2;
if(value(lines[idx][mid-1],x) > value(lines[idx][mid], x)) left = mid;
else right = mid;
}
return value(lines[idx][left], x);
};
vi ans(N, inf);
ans[0] = 0;
for(auto el: data){
ll now = el.second;
ll n_v = now;
while(true){
ans[now] = std::min(ans[now], calc(n_v, distance(now, n_v)));
if(c_par[n_v] == -1) break;
n_v = c_par[n_v];
}
n_v = now;
while(true){
add_line(n_v, mp(B[now], A[now]+ans[now]+distance(now, n_v)*B[now]));
if(c_par[n_v] == -1) break;
n_v = c_par[n_v];
}
}
rep(now,0,N){
ll n_v = now;
while(true){
ans[now] = std::min(ans[now], calc(n_v, distance(now, n_v)));
if(c_par[n_v] == -1) break;
n_v = c_par[n_v];
}
}
{
reverse(all(ans));
ans.pop_back();
reverse(all(ans));
}
return ans;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 1ms
memory: 3784kb
input:
2 684124582850 713748627948 74361 256955 0 1 661088
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 733283747618 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 3 lines
Test #2:
score: -7
Wrong Answer
time: 1ms
memory: 3664kb
input:
3 251115773325 363097865287 358609487841 826785 213106 914768 0 1 851938 2 0 231697
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 955485332655 1549512318252 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
wrong answer 3rd lines differ - expected: '442679377470', found: '1549512318252'
Subtask #2:
score: 0
Wrong Answer
Test #31:
score: 0
Wrong Answer
time: 292ms
memory: 51956kb
input:
100000 746699125678 374834842799 250803643493 620187038832 454433387570 406226564003 897157438699 99473514061 734784419618 503968957100 363935477037 277126009840 52078020050 990757079812 847235285349 950784717285 271017141367 861087225700 996035427219 520682200664 282013988419 415183977876 882007771...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 1148030742334 1636760433058 2131282232650 2353514637869 2672707119337 2885076006601 2948215735597 3003888852169 3054019822989 3117708941277 3168979051095 3214001638323 3269286229765 3273106480907 3287227043365 3335909595067 3361857042147 3364657567217 338173015...
result:
wrong answer 7th lines differ - expected: '2763307672337', found: '2885076006601'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 17
Accepted
time: 115ms
memory: 37412kb
input:
100000 15175010 23519365 21177669 27079342 9089 16784452 29693960 23124925 17048604 10179491 12828214 24992902 8483134 2928073 23807522 7332137 17421520 28460746 1607282 13224363 11900728 11794692 11495061 4687109 23460275 7657982 27417256 16978162 7326803 23083826 24942987 16610314 12147303 2828271...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 16705757 ...
result:
ok 100001 lines
Test #70:
score: -17
Wrong Answer
time: 154ms
memory: 37904kb
input:
100000 3100890 18869608 28100950 22925442 5793993 25887606 5712025 16783243 22490605 7223603 27212909 19749276 22470322 1196820 23308444 12318305 13271014 12850212 19296071 20606196 7506157 10805123 4563831 23592776 15092259 13668900 4494974 28314546 9688373 16660275 26653405 20265376 23328402 65821...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17254147 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 17520670 ...
result:
wrong answer 2nd lines differ - expected: '10152436', found: '17520670'
Subtask #5:
score: 0
Wrong Answer
Test #94:
score: 0
Wrong Answer
time: 78ms
memory: 37000kb
input:
99281 551670361798 568902251563 418071776626 697635341894 641578820039 117221079324 812766431051 425410617978 663769685693 282144284527 799662290178 749088952784 586626406385 122473825417 459510657357 871705247919 443707710712 735612808044 237919555727 829939639783 122127143240 616906466299 24431898...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1...
result:
wrong answer 2nd lines differ - expected: '598598746654', found: '1152921504606846976'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%