| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131814 |
2019-07-17T17:05:06 Z |
futurer |
Toll (APIO13_toll) |
C++14 |
|
21 ms |
16888 KB |
// in the name of ALLAH
#pragma GCC optimize "unroll-loops"
#pragma GCC optimize "-O3"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 6e5+5, M = 6e5+5, L = 21, inf = 1e8;
ll W[N], SZ[N], rt;
int D[N], C[M], PR[M], A[M], B[M], dp[N], H[N], P[N], n, m, k, pr, cent;
vector<int> adj[N], v;
int get(int a) { return(!D[a]?a:D[a]=get(D[a])); }
inline void merg(int a, int b){
a=get(a); b=get(b);
if(a^b) D[b]=a;
}
bitset<M> AYA, DID;
bool cmp(int&a, int&b) { return(C[a]<C[b]); }
void DFS(int u){
DID[u]=1;
W[cent]+=W[u];
merg(cent, u);
for(int x:adj[u]) if(!DID[x]) DFS(x);
}
void DFS2(int u, int p){
H[u]=H[P[u]=p]+1;
for(int x:adj[u]) if(A[x]^B[x]^u^p){
int to=A[x]^B[x]^u;
if(x>=m) dp[to]=inf;
DFS2(to, u);
}
}
ll DFS3(int u, int p){
ll ah=0;
SZ[u]=W[u];
for(int x:adj[u]) if(A[x]^B[x]^u^p){
int to=A[x]^B[x]^u;
ah+=DFS3(to, u);
ah+=1LL*SZ[to]*dp[to];
SZ[u]+=SZ[to];
}
return(ah);
}
void ah() { cerr << "!!!\n"; }
int32_t main(){
scanf("%d %d %d", &n, &m, &k);
for(int i=0;i<m;i++){
scanf("%d %d %d", &A[i], &B[i], &C[i]);
PR[pr++]=i;
}
for(int i=m;i<m+k;i++) scanf("%d %d", &A[i], &B[i]);
for(int i=1;i<=n;i++) scanf("%lld", &W[i]);
sort(PR, PR+pr, cmp);
for(int i=0;i<pr;i++) if(get(A[PR[i]])^get(B[PR[i]])){
merg(A[PR[i]], B[PR[i]]);
AYA[PR[i]]=1;
}
memset(D, 0, sizeof(D));
for(int i=m;i<m+k;i++) PR[pr++]=i;
sort(PR, PR+pr, cmp);
for(int i=0;i<pr;i++) if(get(A[PR[i]])^get(B[PR[i]])){
merg(A[PR[i]], B[PR[i]]);
if(PR[i]<m){
adj[A[PR[i]]].push_back(B[PR[i]]);
adj[B[PR[i]]].push_back(A[PR[i]]);
}
}
memset(D, 0, sizeof(D));
cent=n;
for(int i=1;i<=n;i++) if(!DID[i]) { cent++; DFS(i); }
for(int i=0;i<N;i++) while(adj[i].size()) adj[i].pop_back();
for(int i=0;i<m+k;i++){
A[i]=get(A[i]);
B[i]=get(B[i]);
}
for(int i=0;i<m;i++) if(AYA[i]&&(A[i]^B[i])){
v.push_back(i);
}
sort(v.begin(), v.end());
memset(D, 0, sizeof(D));
for(int msk=0;msk<(1<<k);msk++){
vector<int> v2;
for(int i=n+1;i<=cent;i++){
D[i]=0;
dp[i]=-1;
while(adj[i].size()) adj[i].pop_back();
}
pr=0;
for(int i=0;i<k;i++) if(msk&(1<<i)) PR[pr++]=m+i;
for(int&x:v) PR[pr++]=x;
bool f=0;
for(int i=0;i<pr;i++){
if(get(A[PR[i]])^get(B[PR[i]])){
merg(A[PR[i]], B[PR[i]]);
adj[A[PR[i]]].push_back(PR[i]);
adj[B[PR[i]]].push_back(PR[i]);
}
else{
if(!AYA[PR[i]]) { f=1; continue; }
v2.push_back(PR[i]);
}
}
if(f) continue;
DFS2(n+1, 0);
for(int&x:v2){
int a=A[x], b=B[x];
while(H[a]>H[b]) { dp[a]=min(dp[a], C[x]); a=P[a]; }
while(H[b]>H[a]) { dp[b]=min(dp[b], C[x]); b=P[b]; }
while(a^b){
dp[a]=min(dp[a], C[x]); dp[b]=min(dp[b], C[x]);
a=P[a]; b=P[b];
}
}
for(int i=n+1;i<=cent;i++) if(!(~dp[i])) dp[i]=0;
rt=max(rt, DFS3(n+1, 0));
}
printf("%lld", rt);
}
Compilation message
toll.cpp: In function 'int32_t main()':
toll.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &A[i], &B[i], &C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:51:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=m;i<m+k;i++) scanf("%d %d", &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:52:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%lld", &W[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 2 |
Correct |
19 ms |
16888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 2 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
16888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 2 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
16888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 2 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
16888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 2 |
Correct |
19 ms |
16888 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
16888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
