| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786424 |
2023-07-18T07:41:32 Z |
반딧불(#10026) |
Paths (RMI21_paths) |
C++17 |
|
521 ms |
58668 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
int cnt[800002]; ll sum[800002];
void update(int i, int l, int r, int x, int v1, ll v2){
if(l==r){
cnt[i] += v1, sum[i] += v2;
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v1, v2);
else update(i*2+1, m+1, r, x, v1, v2);
cnt[i] = cnt[i*2] + cnt[i*2+1], sum[i] = sum[i*2] + sum[i*2+1];
}
ll query(int i, int l, int r, int x){
if(l==r) return cnt[i] ? (sum[i] / cnt[i]) * x : 0;
int m = (l+r)>>1;
if(cnt[i*2+1] >= x) return query(i*2+1, m+1, r, x);
else return query(i*2, l, m, x-cnt[i*2+1]) + sum[i*2+1];
}
} tree;
struct Edge{
int s, e; ll v; int idx;
Edge(){}
Edge(int s, int e, ll v): s(s), e(e), v(v){}
bool operator<(const Edge &r)const{
return idx<r.idx;
}
};
int n, k;
Edge arr[200002];
vector<Edge> link[100002];
int in[100002], out[100002], idx[100002], inCnt;
int par[100002];
void dfs_in(int x, int p=-1){
in[x] = ++inCnt;
idx[inCnt] = x;
par[x] = p;
for(auto y: link[x]){
if(y.e == p) continue;
dfs_in(y.e, x);
}
out[x] = inCnt;
}
vector<Edge> linkSet[100002];
ll MX[200002], where[200002]; /// �� ���� �������� ���� �� �ִ밡 ���ΰ�
vector<pair<ll, ll> > options[100002]; /// �� �������� ���� �� �ִ� ��� �ɼ�
pair<ll, int> dfs_getValues(int x, int p=-1){
// printf("Get value %d %d\n", x, p);
if(!linkSet[x].empty()){
vector<Edge> tlst;
for(Edge y: linkSet[x]){
if((y.idx ^ p) == 1){
tlst.push_back(y);
continue;
}
options[x].push_back(make_pair(MX[y.idx] = (dfs_getValues(y.e, y.idx).first + y.v), y.idx));
}
linkSet[x].swap(tlst);
sort(options[x].begin(), options[x].end());
options[x].erase(unique(options[x].begin(), options[x].end()), options[x].end());
reverse(options[x].begin(), options[x].end());
}
if(options[x].empty()) return make_pair(0, -1);
else if((options[x][0].second ^ p) != 1) return options[x][0];
else if((int)options[x].size() == 1) return make_pair(0, -1);
else return options[x][1];
}
vector<ll> numbers;
vector<int> inQuery[100002], outQuery[100002];
ll ans[100002];
void putQuery(int s, int e, ll p, int mode){
if(in[s] < in[e]){
if(mode == 1){
inQuery[1].push_back(p), outQuery[in[e]].push_back(p);
if(out[e]+1 <= n+1) inQuery[out[e]+1].push_back(p), outQuery[n+1].push_back(p);
}
else{
outQuery[1].push_back(p), inQuery[in[e]].push_back(p);
if(out[e]+1 <= n+1) outQuery[out[e]+1].push_back(p), inQuery[n+1].push_back(p);
}
}
else{
if(mode == 1) inQuery[in[s]].push_back(p), outQuery[out[s]+1].push_back(p);
else outQuery[in[s]].push_back(p), inQuery[out[s]+1].push_back(p);
}
}
int main(){
scanf("%d %d", &n, &k);
for(int i=1; i<n; i++){
scanf("%d %d %lld", &arr[i*2-2].s, &arr[i*2-2].e, &arr[i*2-2].v);
arr[i*2-1].s = arr[i*2-2].e, arr[i*2-1].e = arr[i*2-2].s, arr[i*2-1].v = arr[i*2-2].v;
arr[i*2-2].idx = i*2-2, arr[i*2-1].idx = i*2-1;
link[arr[i*2-2].s].push_back(arr[i*2-2]);
link[arr[i*2-1].s].push_back(arr[i*2-1]);
}
for(int i=1; i<=n; i++) linkSet[i] = link[i];
dfs_in(1);
for(int i=0; i<(n-1)*2; i++){
pair<ll, int> p = dfs_getValues(arr[i].e, i);
MX[i] = p.first + arr[i].v;
where[i] = p.second;
}
for(int i=1; i<=n; i++) options[i].clear();
for(int i=0; i<(n-1)*2; i++){
options[arr[i].s].push_back(make_pair(MX[i], i));
}
for(int i=1; i<=n; i++) sort(options[i].rbegin(), options[i].rend());
for(int i=1; i<=n; i++){
/// ���� �ִ� 2N��
for(int j=0; j<(int)options[i].size(); j++){
int p = options[i][j].second; ll v = options[i][j].first;
int s = arr[p].s, e = arr[p].e;
putQuery(s, e, v, 1);
if(where[p] != -1) putQuery(s, e, v-arr[p].v, -1);
}
}
for(int i=1; i<=n; i++) for(int p: inQuery[i]) numbers.push_back(p);
for(int i=1; i<=n; i++) for(int p: outQuery[i]) numbers.push_back(p);
sort(numbers.begin(), numbers.end());
numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
for(int i=1; i<=n; i++) for(int &p: inQuery[i]) p = lower_bound(numbers.begin(), numbers.end(), p) - numbers.begin();
for(int i=1; i<=n; i++) for(int &p: outQuery[i]) p = lower_bound(numbers.begin(), numbers.end(), p) - numbers.begin();
int L = (int)numbers.size();
for(int i=1; i<=n; i++){
for(int p: inQuery[i]){
// printf("In update %d %lld\n", i, numbers[p]);
tree.update(1, 0, L-1, p, 1, numbers[p]);
}
for(int p: outQuery[i]){
// printf("Out update %d %lld\n", i, numbers[p]);
tree.update(1, 0, L-1, p, -1, -numbers[p]);
}
ans[idx[i]] = tree.query(1, 0, L-1, k);
}
for(int i=1; i<=n; i++){
printf("%lld\n", ans[i]);
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%d %d %lld", &arr[i*2-2].s, &arr[i*2-2].e, &arr[i*2-2].v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
521 ms |
58668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
