QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232438 | #5313. Please Save Pigeland | Alish | RE | 5ms | 20088kb | C++17 | 3.4kb | 2023-10-30 14:17:09 | 2023-10-30 14:17:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
ll mod = 1e9+7 ;
const int N = 5e5+23;
const ll INF=LLONG_MAX;
vector<pll> g[N];
ll distu[N], distd[N], sz[N], is[N];
pll dpd[N], dpu[N]; // for GCD
int n, k;
void dfs(int v, int p=0){
for (auto pp: g[v]){
int u=pp.F;
ll w=pp.S;
if(u==p )continue;
dfs(u, v);
distd[v]+=w*sz[u]+distd[u];
sz[v]+=sz[u];
pll temp= dpd[u];
if(temp.F || is[u])temp.F+=w;
if(dpd[v].F==0 && dpd[v].S==0 && !is[v]) {dpd[v]=temp; continue;}
if(temp.F< dpd[v].F ) swap(temp, dpd[v]);
dpd[v].S=__gcd(__gcd(dpd[v].S, temp.S), temp.F-dpd[v].F);
}
}
void DFS(int v, int p=0){
pll pref[g[v].size()+23], suff[g[v].size()+23];
pref[0]=dpu[v]; suff[g[v].size()-1]=dpu[v];
for (int i=0; i<g[v].size(); i++){
int u=g[v][i].F;
ll w=g[v][i].S;
if(u==p) {pref[i+1]=pref[i]; continue; }
pll r1=pref[i];
pll r2=dpd[u];
if(r2.F|| is[u])r2.F+=w;
if(r1.F>r2.F) swap(r1, r2);
if(r1.F==0 && r1.S==0){
pref[i+1]=r2;
continue;
}
pref[i+1].F=r1.F;
pref[i+1].S=__gcd(__gcd(r1.S, r2.S), r2.F-r1.F);
}
for (int i=g[v].size()-1; i>0; i--){
int u=g[v][i].F;
ll w=g[v][i].S;
if(u==p) {suff[i-1]=suff[i]; continue; }
pll r1=suff[i];
pll r2=dpd[u];
if(r2.F || is[u])r2.F+=w;
if(r1.F>r2.F) swap(r1, r2);
if(r1.F==0 && r1.S==0){
suff[i-1]=r2;
continue;
}
suff[i-1].F=r1.F;
suff[i-1].S=__gcd(__gcd(r1.S, r2.S), r2.F-r1.F);
}
for (int i=0; i<g[v].size(); i++){
int u=g[v][i].F;
ll w=g[v][i].S;
if(u==p) continue;
pll r1=pref[i];
pll r2=suff[i];
if(r1.F || is[v]) r1.F+=w;
if(r2.F || is[v]) r2.F+=w;
if(r1.F>r2.F) swap(r1, r2);
if(is[u]){
dpu[u].F=0;
dpu[u].S=__gcd(__gcd(r1.F, r1.S), __gcd(r2.F, r2.S));
}
else if(r1.F==0 && r1.S==0) dpu[u]=r2;
else{
dpu[u].F=r1.F;
dpu[u].S=__gcd(__gcd(r1.S, r2.S), r2.F-r1.F);
}
distu[u]=distu[v]+distd[v]-distd[u]+(k-sz[u])*w- w*sz[u];
DFS(u, v);
}
}
int main()
{
cin>>n>>k;
for (int i=0; i<k; i++){int v; cin>>v; sz[v]++; is[v]++;}
for (int i=0; i<n-1; i++){
int u, v; cin>>v>>u;
ll w; cin>>w;
g[v].pb({u, w}); g[u].pb({v, w});
}
dfs(1);
DFS(1);
ll ans=INF;
for (int v=1; v<=n; v++){
ans=min( ans, (distd[v]+distu[v])/__gcd(__gcd(dpd[v].F, dpd[v].S), __gcd(dpu[v].F, dpu[v].S)));
//cout<<__gcd(__gcd(dpd[v].F, dpd[v].S), __gcd(dpu[v].F, dpu[v].S))<<" "<<distd[v]+distu[v]<<endl;
}
cout<<ans*2<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 19900kb
input:
5 3 3 4 5 1 2 2 2 3 4 2 5 4 3 4 6
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 20088kb
input:
10 3 1 7 10 7 6 3 1 8 3 3 6 3 8 6 2 4 1 1 10 6 4 2 8 3 9 10 3 5 10 3
output:
24
result:
ok 1 number(s): "24"
Test #3:
score: -100
Runtime Error
input:
1 1 1