結果

問題 No.1002 Twotone
ユーザー miyo2580miyo2580
提出日時 2023-10-10 21:34:02
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,239 bytes
コンパイル時間 3,610 ms
コンパイル使用メモリ 274,600 KB
実行使用メモリ 62,516 KB
最終ジャッジ日時 2024-09-13 00:37:17
合計ジャッジ時間 17,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 2 ms
6,940 KB
testcase_07 WA -
testcase_08 AC 346 ms
22,712 KB
testcase_09 AC 353 ms
22,916 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 2 ms
6,940 KB
testcase_15 WA -
testcase_16 AC 698 ms
24,100 KB
testcase_17 WA -
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 570 ms
34,088 KB
testcase_20 AC 680 ms
50,692 KB
testcase_21 AC 663 ms
49,296 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 517 ms
29,232 KB
testcase_24 AC 967 ms
44,876 KB
testcase_25 AC 928 ms
44,564 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 72 ms
22,440 KB
testcase_28 AC 140 ms
30,536 KB
testcase_29 AC 117 ms
29,224 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 113 ms
29,936 KB
testcase_32 AC 138 ms
28,840 KB
testcase_33 AC 112 ms
29,228 KB
testcase_34 AC 1,963 ms
62,516 KB
権限があれば一括ダウンロードができます

ソースコード

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);
        }
        }
      };
      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){
        if(CY>=3)efs(CX,CY);
      }
    };
    efs(0,n);
    cout<<ans<<endl;
    return 0;
}
0