oj.uz

답안 #778604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778604 2023-07-10T13:13:44 Z 1075508020060209tc Janjetina (COCI21_janjetina) C++14
35 / 110
 298 ms 31344 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int lowbit(int x){return x&-x;}
int bit[1000006];
stack<int>stk;
void upd(int pl,int v){
while(pl<=1000000){
    bit[pl]+=v;
    pl+=lowbit(pl);
}
}
int qsum(int pl){
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}
int n;int K;
vector<pair<int,int>>e[500005];
int psmx[500005];
int dph[500005];
int vis[500005];
int sbsz[500005];
int fa[500005];

void dfssz(int nw,int pa){
sbsz[nw]=1;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i].first;
    if(v==pa||vis[v]){continue;}
    dfssz(v,nw);
    sbsz[nw]+=sbsz[v];
}
}
void fincen(int nw,int pa,int &cen,int tot){
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i].first;
    if(v==pa||vis[v]){continue;}
    fincen(v,nw,cen,tot);
}
if(cen==0&&sbsz[nw]*2>=tot){
    cen=nw;
}
}
int ans;
void dfsmx(int nw,int pa){
    fa[nw]=pa;
    dph[nw]=dph[pa]+1;
    for(int i=0;i<e[nw].size();i++){
        int v=e[nw][i].first;int w=e[nw][i].second;
        if(v==pa||vis[v]){continue;}
        w=max(w,psmx[nw]);
        psmx[v]=w;
        dfsmx(v,nw);
    }
}


void solve(int rt){
int cen=0;
dfssz(rt,0);
fincen(rt,0,cen,sbsz[rt]);
psmx[cen]=-1e9;
dfsmx(cen,0);
//cout<<cen<<endl;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
for(int i=0;i<e[cen].size();i++){
    int v=e[cen][i].first;
    if(vis[v]){continue;}
    pq.push({psmx[v],v});
}
//upd(1,1);
while(pq.size()){

    int nw=pq.top().second;
  //  cout<<nw<<endl;
    pq.pop();

    int cal=psmx[nw]-(dph[nw]-1)-K;
    if(cal==0){ans++;}
    if(cal>0){
        ans++;
        ans+=qsum(cal+1);
        ans-=min(cal,dph[nw]-2);
    }
    for(int i=0;i<e[nw].size();i++){
        int v=e[nw][i].first;
        if(v==fa[nw]||vis[v]){continue;}
        pq.push({psmx[v],v});
    }
    upd(dph[nw],1);
    stk.push(dph[nw]);
}
while(stk.size()){
    upd(stk.top(),-1);
    stk.pop();
}
vis[cen]=1;
//cout<<cen<<endl;
for(int i=0;i<e[cen].size();i++){
    int v=e[cen][i].first;
    if(vis[v]){continue;}
    solve(v);
}


}



signed main(){
cin>>n>>K;
for(int i=1;i<=n-1;i++){
    int a;int b;int c;
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
}
ans=0;
solve(1);
cout<<ans*2<<endl;

}

Compilation message

Main.cpp: In function 'void dfssz(long long int, long long int)':
Main.cpp:33:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
Main.cpp: In function 'void fincen(long long int, long long int, long long int&, long long int)':
Main.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
Main.cpp: In function 'void dfsmx(long long int, long long int)':
Main.cpp:54:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp: In function 'void solve(long long int)':
Main.cpp:72:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 | for(int i=0;i<e[cen].size();i++){
      |             ~^~~~~~~~~~~~~~
Main.cpp:91:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp:105:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 | for(int i=0;i<e[cen].size();i++){
      |             ~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11976 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 9 ms 12324 KB Output is correct
5 Correct 8 ms 12324 KB Output is correct
6 Correct 8 ms 12252 KB Output is correct
7 Correct 8 ms 12200 KB Output is correct
8 Correct 8 ms 12244 KB Output is correct
9 Correct 7 ms 12244 KB Output is correct
10 Incorrect 8 ms 12196 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12076 KB Output is correct
3 Correct 7 ms 12060 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 29 ms 13992 KB Output is correct
6 Correct 140 ms 21740 KB Output is correct
7 Correct 258 ms 30868 KB Output is correct
8 Correct 272 ms 31324 KB Output is correct
9 Correct 265 ms 30992 KB Output is correct
10 Correct 270 ms 31236 KB Output is correct
11 Correct 255 ms 30816 KB Output is correct
12 Correct 280 ms 31344 KB Output is correct
13 Correct 266 ms 30924 KB Output is correct
14 Correct 298 ms 31272 KB Output is correct
15 Correct 268 ms 31080 KB Output is correct
16 Correct 275 ms 31188 KB Output is correct
17 Correct 274 ms 31264 KB Output is correct
18 Correct 283 ms 31160 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11976 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 9 ms 12324 KB Output is correct
5 Correct 8 ms 12324 KB Output is correct
6 Correct 8 ms 12252 KB Output is correct
7 Correct 8 ms 12200 KB Output is correct
8 Correct 8 ms 12244 KB Output is correct
9 Correct 7 ms 12244 KB Output is correct
10 Incorrect 8 ms 12196 KB Output isn't correct
11 Halted 0 ms 0 KB -