Submission #1277894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277894		uzukishinobu	Transport (COCI19_transport)	C++20	0 / 100	0 ms	0 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int n;
vector <pair<int,int>> z[1000005];
int t[1000005];
int del[1000005];
int child[1000005];
int sz;
vector <int> v;
int sad;
vector <int> pre;
void predfs(int i,int par){
     child[i]=1;
     for (auto p:z[i]){
          if (p.first==par || del[p.first]){
              continue;
          }
          predfs(p.first,i);
          child[i]+=child[p.first];
     }
}
int centroid(int i,int par){
    for (auto p:z[i]){
         if (p.first==par || del[p.first]){
             continue;
         }
         if (child[p.first]*2>sz){
             return centroid(p.first,i);
         }
    }
    return i;
}
void dfs1(int i,int par,int min1,int cur){
    min1=min(min1,cur);
    v.push_back(min1);
    cur+=t[i];
    for (auto [p,w]:z[i]){
         if (p==par || del[p]){
             continue;
         }
         dfs1(p,i,min1,cur-w);
    }
}
void sadge(int i){
    predfs(i,0);
    sz=child[i];
    int cen=centroid(i,0);
    del[cen]=1;
    for (auto [p,w]:z[cen]){
         if (del[p]){
             continue;
         }
         dfs1(p,cen,-w,-w);
    }
    for (auto [p,w]:z[cen]){
         if (del[p]){
             continue;
         }
         sadge(p);
    }
}

struct BIT{
      int bit[4000005]={0};
      vector <int> del;
      void update(int i,int val){
          i++;
          while (i<=n+128){
               if (bit[i]==0){
                   del.push_back(i);
               }
               bit[i]+=val;
               i+=i&-i;
          }
      }
      int query(int i){
          i++;
          int res=0;
          while (i>0){
               res+=bit[i];
               i-=i&-i;
          }
          return res;
      }
      void reset(){
          for (auto p:del){
               bit[p]=0;
          }
          del.clear();
      }
};
BIT d;
int res=0;
void dfs(int i,int par,int cen,int min1,int cur,int cur1){
    min1=min(min1,cur);
    if (t[i]>=abs(min(0LL,cur1))){
        int pre1=t[i]+cur+t[cen];
        res+=(sad==0);
//        if (cen==2 && !sad){
//            cout << i << "\n";
//        }
        int pos=lower_bound(v.begin(),v.end(),-pre1)-v.begin();
        res+=max(0LL,d.query(n)-(d.query(pos)));
    }
    {
        int val=min1;
        int pos=lower_bound(v.begin(),v.end(),val)-v.begin()+1;
        pre.push_back(pos);
    }
    cur+=t[i];
    cur1+=t[i];
    cur1=min(cur1,0LL);
    for (auto [p,w]:z[i]){
         if (p==par || del[p]){
             continue;
         }
         dfs(p,i,cen,min1,cur-w,cur1-w);
    }
}
void decompose(int i){
    predfs(i,0);
    sz=child[i];
    int cen=centroid(i,0);
    del[cen]=1;
    d.reset();
    for (auto [p,w]:z[cen]){
         if (del[p]){
             continue;
         }
         dfs(p,cen,cen,-w,-w,-w);
         for (auto p1:pre){
              d.update(p1,1);
         }
         pre.clear();
//         if (cen==2 && !sad){
//             cout << p << " " << res << "\n";
//         }
    }
    if (!sad){
        int pos=lower_bound(v.begin(),v.end(),-t[cen])-v.begin();
        res+=max(0LL,d.query(n)-(d.query(pos)));
//        cout << cen << " " << res << "\n";
    }

    for (auto [p,w]:z[cen]){
         if (del[p]){
             continue;
         }
         decompose(p);
    }
}
signed main()
{
//        freopen("test.txt", "r", stdin);
//    freopen("o2.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         cin >> t[i];
    }
    for (int i=1;i<a;i++){
         int x,y,w;
         cin >> x >> y >> w;
         z[x].push_back({y,w});
         z[y].push_back({x,w});
    }
    sadge(1);
    for (int i=1;i<=a;i++){
         del[i]=0;
    }
    v.push_back(0);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    n=v.size();
    decompose(1);
    sad=1;
    for (int i=1;i<=a;i++){
         del[i]=0;
    }
    for (int i=1;i<=a;i++){
         reverse(z[i].begin(),z[i].end());
    }
    decompose(1);
    cout << res << "\n";
    return 0;
}


/*
6
3 3 6 7 6 5
2 1 5
3 1 2
4 3 9
5 2 2
6 3 5


*/

/*
    freopen("test.txt", "r", stdin);
    freopen("o2.out", "w", stdout);
*/

• Subtask 1: 0 / 100