結果
| 問題 | No.1718 Random Squirrel |
| ユーザー |
 riano
|
| 提出日時 | 2021-10-22 23:24:48 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,211 bytes |
| コンパイル時間 | 2,045 ms |
| コンパイル使用メモリ | 186,044 KB |
| 実行使用メモリ | 40,788 KB |
| 最終ジャッジ日時 | 2024-09-23 07:55:26 |
| 合計ジャッジ時間 | 5,487 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 19 WA * 12 |
コンパイルメッセージ
main.cpp: In member function 'void tree::dfs_(long long int, long long int, bool)':
main.cpp:124:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
124 | for(auto[nx,cost]:G[s]){
| ^
main.cpp: In member function 'std::vector<long long int> tree::adj(long long int)':
main.cpp:198:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
198 | for(auto[x,c]:G[i]){
| ^
main.cpp: In function 'int main()':
main.cpp:226:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
226 | auto[u,v] = ed[i];
| ^
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long long#define rep(i,n) for(int i=0;i<n;i++)#define Pr pair<ll,ll>#define Tp tuple<int,int,int>#define all(v) v.begin(),v.end()#define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr)using Graph = vector<vector<ll>>;const ll mod = 998244353;template<uint64_t mod>struct modint{uint64_t val;constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){}constexpr modint operator-() const noexcept{return modint(*this)=mod-val;}constexpr modint operator+(const modint rhs) const noexcept{return modint(*this)+=rhs;}constexpr modint operator-(const modint rhs) const noexcept{return modint(*this)-=rhs;}constexpr modint operator*(const modint rhs) const noexcept{return modint(*this)*=rhs;}constexpr modint operator/(const modint rhs) const noexcept{return modint(*this)/=rhs;}constexpr modint &operator+=(const modint rhs) noexcept{val+=rhs.val;val-=((val>=mod)?mod:0);return (*this);}constexpr modint &operator-=(const modint rhs) noexcept{val+=((val<rhs.val)?mod:0);val-=rhs.val;return (*this);}constexpr modint &operator*=(const modint rhs) noexcept{val=val*rhs.val%mod;return (*this);}constexpr modint &operator/=(modint rhs) noexcept{uint64_t ex=mod-2;modint now=1;while(ex){now*=((ex&1)?rhs:1);rhs*=rhs,ex>>=1;}return (*this)*=now;}modint & operator++(){val++;if (val == mod) val = 0;return *this;}modint operator++(int){modint<mod> res = *this;++*this;return res;}constexpr bool operator==(const modint rhs) noexcept{return val==rhs.val;}constexpr bool operator!=(const modint rhs) noexcept{return val!=rhs.val;}friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{return os<<(x.val);}friend constexpr istream &operator>>(istream& is,modint& x) noexcept{uint64_t t;is>>t,x=t;return is;}};typedef modint<mod> mint;vector<bool> val(100001,false);vector<ll> sum(100001);//tree#define type long longtype el = 0LL;vector<type> emp = {};struct tree {long long N;vector<vector<pair<long long,long long>>> G;vector<long long> depth;vector<long long> subtree_size;vector<long long> deg;vector<long long> par;vector<int> vis;vector<type> dp;vector<vector<type>> dp_cand;long long len;long long euler_time;long long limit_len = 2e9;vector<long long> from_e1;vector<long long> from_e2;long long cen,end1,end2,diam;tree(long long n) {N = n;G = vector<vector<pair<long long,long long>>>(N);depth = vector<long long>(N,-1);par = vector<long long>(N,-1);subtree_size = vector<long long>(N,1);deg = vector<long long>(N,0);}//DP 操作: 書き換え必須void dp_operation(long long s){if(par[s]!=-1){val[par[s]] = (val[par[s]]|val[s]);}}//Euler Tour で何かする場合は書き足すvoid dfs_(long long s,long long i,bool dp_){len++;euler_time++;for(auto[nx,cost]:G[s]){if(len>=limit_len) break;if(vis[nx]==i) continue;if(!val[nx]){sum[nx] = sum[s]+1;}depth[nx] = depth[s] + cost;vis[nx] = i;par[nx] = s;dfs_(nx,i,dp_);}if(par[s]!=-1){subtree_size[par[s]] += subtree_size[s];}if(dp_) dp_operation(s);len--;}//c は辺の重みvoid unite(long long a,long long b,long long c = 1){G[a].emplace_back(b,c);G[b].emplace_back(a,c);deg[a]++; deg[b]++;}//lim は探索長さ制限 dfs_count は探索累積回数（前回訪問済情報を残す場合）void dfs(long long rt,bool dp_ = false,long long lim = 2e9,long long dfs_count = 0){if(dfs_count==0) vis.assign(N,-1);if(dp_){dp.assign(N,el);dp_cand.assign(N,emp);}limit_len = lim;euler_time = -1;len = -1;vis[rt] = dfs_count; depth[rt] = 0;dfs_(rt,dfs_count,dp_);}long long diameter(void){dfs(1);from_e2 = depth;long long mx = -1;for(int i=0;i<N;i++){if(from_e2[i]>mx){end1 = i; mx = from_e2[i];}}dfs(end1);from_e1 = depth;mx = -1;for(int i=0;i<N;i++){if(from_e1[i]>mx){end2 = i; mx = from_e1[i];}}dfs(end2);from_e2 = depth;diam = mx;return diam;}long long center(void){for(int i=0;i<N;i++){if(from_e1[i]==from_e2[i]&&from_e2[i]==diam/2){cen = i; break;}}return cen;}vector<long long> adj(long long i){vector<long long> res;for(auto[x,c]:G[i]){res.push_back(x);}return res;}};int main() {riano_; ll ans = 0;ll N,K; cin >> N >> K;//main関数内でtree tr(N+1),tr2(N+1);vector<Pr> ed;rep(i,N-1){ll u,v; cin >> u >> v;tr.unite(u,v);ed.push_back(make_pair(u,v));}ll rt = 0;rep(i,K){ll d; cin >> d; rt = d;val[d] = true;}tr.dfs(rt,true);ll all = 0;rep(i,N-1){auto[u,v] = ed[i];if(val[u]&val[v]){tr2.unite(u,v);all += 2;}}tr2.diameter();rep(i,N){if(val[i+1]){sum[i+1] = all-max(tr2.from_e1[i+1],tr2.from_e2[i+1]);}}tr.dfs(rt);rep(i,N){cout << sum[i+1] << "\n";}//cout << ans << endl;}