結果

問題 No.1002 Twotone
ユーザー miyo2580miyo2580
提出日時 2023-10-10 21:28:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,285 bytes
コンパイル時間 3,105 ms
コンパイル使用メモリ 231,216 KB
実行使用メモリ 28,812 KB
最終ジャッジ日時 2024-09-13 00:22:19
合計ジャッジ時間 12,247 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 502 ms
19,112 KB
testcase_04 AC 705 ms
23,784 KB
testcase_05 AC 619 ms
23,260 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
using Graph = vector<vector<ll>>;
const long long INF = 1LL<<60;
const long long MOD = 1000000007;

int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,k;
    cin>>n>>k;
    vector<vector<P>> g(n);
    rep(i,n-1){
      ll a,b,c;
      cin>>a>>b>>c;
      a--;b--;
      g[a].push_back({b,c});
      g[b].push_back({a,c});
    }
    vec dead(n);
    vec par(n);
    vec sub(n);
    vec cen;
    ll ans=0;
    map<ll,ll> A,B;
    map<P,ll> C;
    ll cnt=0;
    function<ll(ll,ll,ll)> dfs=[&](ll x,ll p,ll size){
      sub[x]=1;
      bool flg=1;
      for(auto[nx,_]:g[x]){
        if(dead[nx])continue;
        if(nx==p)continue;
        par[nx]=x;
        sub[x]+=dfs(nx,x,size);
        if(sub[nx]>size/2)flg=0;
      }
      if(size-sub[x]>size/2)flg=0;
      if(flg)cen.push_back(x);
      return sub[x];
    };
    function<void(ll,ll)> efs=[&](ll x,ll size){
      vector<P> memo;
      cen.clear();
      dfs(x,-1,size);
      assert(!cen.empty());
      dead[cen[0]]=1;
      A.clear();
      B.clear();
      C.clear();
      cnt=0;
      map<ll,ll> CA,CB;
      map<P,ll> CC;
      ll ccnt=0;
      function<void(ll,ll,P)> ffs=[&](ll x,ll p,P id){
        for(auto[cx,cy]:g[x]){
           if(cx==p)continue;
           if(dead[cx])continue;
           P cid=id;
           if(id.first==-1&&id.second!=cy){
              cid.first=cy;
              ans++;
              if(cid.first>cid.second)swap(cid.first,cid.second);
              ans+=C[cid];
              ans+=A[cid.first];
              ans+=A[cid.second];
              CC[cid]++;
              CB[cid.first]++;
              CB[cid.second]++;
              ffs(cx,x,cid);
        }
        else if(id.first==-1&&id.second==cy){
              ans+=B[id.second];
              ans+=cnt-A[id.second];
              CA[id.second]++;
              ccnt++;
              ffs(cx,x,id);
        }
        else if(id.first!=-1&&(id.first==cy||id.second==cy)){
              ans++;
              ans+=C[id];
              ans+=A[id.first];
              ans+=A[id.second];
              CC[id]++;
              CB[id.first]++;
              CB[id.second]++;
              ffs(cx,x,id);
        }
        else{
          ffs(cx,x,{INF,INF});
        }
        }
      };
      for(auto[cx,cy]:g[cen[0]]){
        if(dead[cx])continue;
        if(cx==par[cen[0]]){
          memo.push_back({cx,size-sub[cen[0]]});
        }
        else memo.push_back({cx,sub[cx]});
        ans+=B[cy];
        ans+=cnt-A[cy];
        ffs(cx,cen[0],{-1,cy});
        for(auto[CX,CY]:CA)A[CX]+=CY;
        for(auto[CX,CY]:CB)B[CX]+=CY;
        for(auto[CX,CY]:CC)C[CX]+=CY;
        cnt+=ccnt;
        cnt++;
        A[cy]++;
        CA.clear();CB.clear();CC.clear();ccnt=0;
      }
      for(auto[CX,CY]:memo){
        efs(CX,CY);
      }
    };
    efs(0,n);
    cout<<ans<<endl;
    return 0;
}
0