結果

問題 No.1002 Twotone
ユーザー miyo2580miyo2580
提出日時 2023-10-10 21:51:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,982 ms / 5,000 ms
コード長 3,227 bytes
コンパイル時間 2,473 ms
コンパイル使用メモリ 196,116 KB
実行使用メモリ 62,584 KB
最終ジャッジ日時 2024-09-13 01:22:27
合計ジャッジ時間 17,698 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 358 ms
18,292 KB
testcase_04 AC 484 ms
22,860 KB
testcase_05 AC 485 ms
22,892 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 212 ms
15,232 KB
testcase_08 AC 381 ms
22,836 KB
testcase_09 AC 398 ms
22,888 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 479 ms
19,632 KB
testcase_12 AC 692 ms
24,420 KB
testcase_13 AC 684 ms
24,448 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 312 ms
15,232 KB
testcase_16 AC 691 ms
24,088 KB
testcase_17 AC 688 ms
24,048 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 532 ms
34,080 KB
testcase_20 AC 665 ms
50,652 KB
testcase_21 AC 676 ms
49,316 KB
testcase_22 AC 3 ms
6,940 KB
testcase_23 AC 519 ms
29,080 KB
testcase_24 AC 1,008 ms
44,600 KB
testcase_25 AC 969 ms
44,692 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 93 ms
22,948 KB
testcase_28 AC 174 ms
29,224 KB
testcase_29 AC 143 ms
29,224 KB
testcase_30 AC 2 ms
6,944 KB
testcase_31 AC 135 ms
28,240 KB
testcase_32 AC 174 ms
28,584 KB
testcase_33 AC 143 ms
28,456 KB
testcase_34 AC 1,982 ms
62,584 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   41 |       for(auto[nx,_]:g[x]){
      |               ^
main.cpp: In lambda function:
main.cpp:65:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   65 |         for(auto[cx,cy]:g[x]){
      |                 ^
main.cpp: In lambda function:
main.cpp:100:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  100 |       for(auto[cx,cy]:g[cen[0]]){
      |               ^
main.cpp:109:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  109 |         for(auto[CX,CY]:CA)A[CX]+=CY;
      |                 ^
main.cpp:110:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  110 |         for(auto[CX,CY]:CB)B[CX]+=CY;
      |                 ^
main.cpp:111:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  111 |         for(auto[CX,CY]:CC)C[CX]+=CY;
      |                 ^
main.cpp:117:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  117 |       for(auto[CX,CY]:memo){
      |               ^

ソースコード

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;
      par[x]=p;
      for(auto[nx,_]:g[x]){
        if(dead[nx])continue;
        if(nx==p)continue;
        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){
        efs(CX,CY);
      }
    };
    efs(0,n);
    cout<<ans<<endl;
    return 0;
}
0