結果

問題 No.1002 Twotone
ユーザー miyo2580miyo2580
提出日時 2023-10-10 21:51:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,134 ms / 5,000 ms
コード長 3,227 bytes
コンパイル時間 2,591 ms
コンパイル使用メモリ 194,416 KB
実行使用メモリ 62,420 KB
最終ジャッジ日時 2023-10-10 21:52:05
合計ジャッジ時間 18,465 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 370 ms
18,020 KB
testcase_04 AC 489 ms
22,720 KB
testcase_05 AC 527 ms
22,712 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 219 ms
14,860 KB
testcase_08 AC 387 ms
22,816 KB
testcase_09 AC 423 ms
22,816 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 507 ms
19,424 KB
testcase_12 AC 739 ms
24,232 KB
testcase_13 AC 720 ms
24,212 KB
testcase_14 AC 2 ms
4,352 KB
testcase_15 AC 342 ms
15,068 KB
testcase_16 AC 741 ms
23,764 KB
testcase_17 AC 740 ms
24,196 KB
testcase_18 AC 2 ms
4,352 KB
testcase_19 AC 577 ms
33,924 KB
testcase_20 AC 723 ms
50,360 KB
testcase_21 AC 704 ms
49,156 KB
testcase_22 AC 2 ms
4,348 KB
testcase_23 AC 579 ms
27,984 KB
testcase_24 AC 1,112 ms
44,356 KB
testcase_25 AC 1,056 ms
43,036 KB
testcase_26 AC 2 ms
4,356 KB
testcase_27 AC 92 ms
22,608 KB
testcase_28 AC 178 ms
29,280 KB
testcase_29 AC 151 ms
29,156 KB
testcase_30 AC 2 ms
4,352 KB
testcase_31 AC 142 ms
29,396 KB
testcase_32 AC 188 ms
29,192 KB
testcase_33 AC 148 ms
29,140 KB
testcase_34 AC 2,134 ms
62,420 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: ラムダ関数内:
main.cpp:41:15: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   41 |       for(auto[nx,_]:g[x]){
      |               ^
main.cpp: ラムダ関数内:
main.cpp:65:17: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   65 |         for(auto[cx,cy]:g[x]){
      |                 ^
main.cpp: ラムダ関数内:
main.cpp:100:15: 警告: 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: 警告: 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: 警告: 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: 警告: 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: 警告: 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