| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 352213 |
2021-01-20T13:39:03 Z |
arnold518 |
Toll (APIO13_toll) |
C++14 |
|
0 ms |
0 KB |
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("avx, avx2, fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int MAXM = 3e5;
const int MAXK = 20;
int N, M, K;
struct Edge
{
int u, v, w;
};
Edge E[MAXM+10];
pii A[MAXK+10];
ll B[MAXN+10];
struct UF
{
int par[MAXN+10], sz[MAXN+10];
void init()
{
for(register int i=1; i<=N; i++)
{
par[i]=i;
sz[i]=1;
}
}
inline int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
x=Find(x); y=Find(y);
if(sz[x]>sz[y]) swap(x, y);
if(sz[x]==sz[y]) sz[y]++;
par[x]=y;
}
}uf, uf2;
ll ans, val=0;
vector<pii> adj[MAXN+10], adj2[MAXN+10];
int root[MAXN+10];
ll sz[MAXN+10];
vector<int> ST;
inline int dfs2(int now, int bef, int k)
{
if(now==k) return 1;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(nxt.second!=-1 && P[nxt.second]==0) ST.push_back(nxt.second);
if(dfs2(nxt.first, now, k)) return 1;
if(nxt.second!=-1 && P[nxt.second]==0) ST.pop_back();
}
return 0;
}
int col[MAXN+10];
ll D[MAXN+10];
int par[30][MAXN+10], dep[MAXN+10], L[MAXN+10], cnt;
inline void dfs3(int now, int bef, int d)
{
L[now]=++cnt;
par[0][now]=bef;
dep[now]=d;
for(auto nxt : adj2[now])
{
if(nxt.first==bef) continue;
dfs3(nxt.first, now, d+1);
}
}
int lca(int u, int v)
{
if(dep[u]>dep[v]) swap(u, v);
for(register int i=20; i>=0; i--) if(dep[u]<=dep[par[i][v]]) v=par[i][v];
if(u==v) return u;
for(register int i=20; i>=0; i--) if(par[i][u]!=par[i][v]) u=par[i][u], v=par[i][v];
return par[0][u];
}
int par2[MAXN+10];
int dep2[MAXN+10];
int val2[MAXN+10];
int Q[MAXN+10];
inline void dfs4(int now, int bef, int d, int k)
{
sz[now]=B[now];
par2[now]=bef;
dep2[now]=d;
val2[now]=k;
for(pii nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs4(nxt.first, now, d+1, nxt.second);
sz[now]+=sz[nxt.first];
}
}
int main()
{
scanf("%d%d%d", &N, &M, &K);
for(register int i=1; i<=M; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
for(register int i=0; i<K; i++) scanf("%d%d", &A[i].first, &A[i].second);
for(register int i=1; i<=N; i++) scanf("%d", &B[i]);
sort(E+1, E+M+1, [&](const Edge &p, const Edge &q)
{
return p.w<q.w;
});
uf.init();
vector<Edge> EE;
for(register int i=1; i<=M; i++)
{
if(uf.Find(E[i].u)==uf.Find(E[i].v)) continue;
uf.Union(E[i].u, E[i].v);
EE.push_back(E[i]);
}
for(register int i=0; i<EE.size(); i++) E[i+1]=EE[i];
M=EE.size();
EE.clear();
assert(M==N-1);
for(register int i=1; i<=M; i++)
{
adj2[E[i].u].push_back({E[i].v, E[i].w});
adj2[E[i].v].push_back({E[i].u, E[i].w});
}
dfs3(1, 1, 1);
for(register int i=1; i<=20; i++) for(register int j=1; j<=N; j++) par[i][j]=par[i-1][par[i-1][j]];
vector<int> VV;
VV.push_back(1);
for(register int i=0; i<K; i++)
{
VV.push_back(A[i].first);
VV.push_back(A[i].second);
}
sort(VV.begin(), VV.end(), [&](const int &p, const int &q)
{
return L[p]<L[q];
});
VV.erase(unique(VV.begin(), VV.end()), VV.end());
int t=VV.size();
for(register int i=0; i+1<t; i++) VV.push_back(lca(VV[i], VV[i+1]));
sort(VV.begin(), VV.end(), [&](const int &p, const int &q)
{
return L[p]<L[q];
});
VV.erase(unique(VV.begin(), VV.end()), VV.end());
sort(VV.begin(), VV.end());
uf.init();
for(auto it : VV) col[it]=it;
for(register int i=1; i<=N; i++) D[i]=B[i];
for(register int i=1; i<=M; i++)
{
if(col[uf.Find(E[i].u)] && col[uf.Find(E[i].v)])
{
EE.push_back(E[i]);
}
else
{
int p=uf.Find(E[i].u), q=uf.Find(E[i].v);
D[p]+=D[q];
uf.par[q]=p;
col[p]|=col[q];
}
}
for(auto &it : EE)
{
it.u=lower_bound(VV.begin(), VV.end(), col[uf.Find(it.u)])-VV.begin()+1;
it.v=lower_bound(VV.begin(), VV.end(), col[uf.Find(it.v)])-VV.begin()+1;
}
for(register int i=0; i<EE.size(); i++) E[i+1]=EE[i];
M=EE.size();
for(register int i=0; i<K; i++)
{
A[i].first=lower_bound(VV.begin(), VV.end(), A[i].first)-VV.begin()+1;
A[i].second=lower_bound(VV.begin(), VV.end(), A[i].second)-VV.begin()+1;
}
for(register int i=0; i<VV.size(); i++)
{
B[i+1]=D[uf.Find(VV[i])];
}
N=VV.size();
/*
printf("VV\n");
for(auto it : VV) printf("%d ", it); printf("\n");
printf("E\n");
for(register int i=1; i<=M; i++) printf("%d %d %d\n", E[i].u, E[i].v, E[i].w);
printf("B\n");
for(register int i=1; i<=N; i++) printf("%lld ", B[i]); printf("\n");
printf("A\n");
for(register int i=0; i<K; i++) printf("%d %d\n", A[i].first, A[i].second);
*/
assert(N<=100);
for(register int i=1; i<(1<<K); i++)
{
vector<int> V;
for(register int j=0; j<K; j++)
{
if(i&(1<<j))
{
V.push_back(j);
}
}
uf.init();
bool flag=true;
for(auto it : V)
{
if(uf.Find(A[it].first)==uf.Find(A[it].second))
{
flag=false;
break;
}
uf.Union(A[it].first, A[it].second);
adj[A[it].first].push_back({A[it].second, it});
adj[A[it].second].push_back({A[it].first, it});
}
if(!flag)
{
for(register int i=1; i<=N; i++) adj[i].clear();
continue;
}
for(register int j=1; j<=M; j++)
{
if(uf.Find(E[j].u)==uf.Find(E[j].v))
{
Q[j]=1;
}
else
{
Q[j]=0;
uf.Union(E[j].u, E[j].v);
adj[E[j].u].push_back({E[j].v, -1});
adj[E[j].v].push_back({E[j].u, -1});
//printf("!%d %d %d\n", E[j].u, E[j].v, 0);
}
}
dfs4(1, 1, 1, -1);
uf2.init();
val=0;
for(register int j=1; j<=N; j++) root[j]=j;
for(register int j=1; j<=M; j++)
{
if(Q[j])
{
int u=E[j].u, v=E[j].v;
u=root[uf2.Find(u)]; v=root[uf2.Find(v)];
while(u!=v)
{
if(dep2[u]>dep2[v]) swap(u, v);
if(val2[v]!=-1) val+=sz[v]*E[j].w;
int t2=root[uf2.Find(par2[v])];
uf2.Union(v, par2[v]);
root[uf2.Find(v)]=t2;
v=t2;
}
}
else
{
int uu=root[uf2.Find(E[j].u)], vv=root[uf2.Find(E[j].v)];
if(dep2[uu]>dep2[vv]) swap(uu, vv);
uf2.Union(vv, uu);
root[uf2.Find(vv)]=uu;
}
}
//if(K>15) continue;
ans=max(ans, val);
for(register int j=1; j<=N; j++) adj[j].clear();
}
printf("%lld\n", ans);
}
Compilation message
toll.cpp:4:39: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
4 | #pragma GCC optimize ("avx, avx2, fma")
| ^
toll.cpp:4:39: warning: bad option '-f avx2' to pragma 'optimize' [-Wpragmas]
toll.cpp:4:39: warning: bad option '-f fma' to pragma 'optimize' [-Wpragmas]
toll.cpp:30:12: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
30 | void init()
| ^
toll.cpp:30:12: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:30:12: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:38:23: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
38 | inline int Find(int x)
| ^
toll.cpp:38:23: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:38:23: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:43:25: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
43 | void Union(int x, int y)
| ^
toll.cpp:43:25: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:43:25: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:59:40: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
59 | inline int dfs2(int now, int bef, int k)
| ^
toll.cpp:59:40: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:59:40: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp: In function 'int dfs2(int, int, int)':
toll.cpp:65:24: error: 'P' was not declared in this scope
65 | if(nxt.second!=-1 && P[nxt.second]==0) ST.push_back(nxt.second);
| ^
toll.cpp:67:24: error: 'P' was not declared in this scope
67 | if(nxt.second!=-1 && P[nxt.second]==0) ST.pop_back();
| ^
toll.cpp: At global scope:
toll.cpp:77:41: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
77 | inline void dfs3(int now, int bef, int d)
| ^
toll.cpp:77:41: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:77:41: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:89:21: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
89 | int lca(int u, int v)
| ^
toll.cpp:89:21: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:89:21: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:103:48: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
103 | inline void dfs4(int now, int bef, int d, int k)
| ^
toll.cpp:103:48: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:103:48: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:117:10: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
117 | int main()
| ^
toll.cpp:117:10: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:117:10: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp: In function 'int main()':
toll.cpp:122:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
122 | for(register int i=1; i<=N; i++) scanf("%d", &B[i]);
| ~^ ~~~~~
| | |
| | ll* {aka long long int*}
| int*
| %lld
toll.cpp:124:51: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
124 | sort(E+1, E+M+1, [&](const Edge &p, const Edge &q)
| ^
toll.cpp:124:51: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:124:51: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:137:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(register int i=0; i<EE.size(); i++) E[i+1]=EE[i];
| ~^~~~~~~~~~
toll.cpp:158:59: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
158 | sort(VV.begin(), VV.end(), [&](const int &p, const int &q)
| ^
toll.cpp:158:59: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:158:59: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:167:59: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
167 | sort(VV.begin(), VV.end(), [&](const int &p, const int &q)
| ^
toll.cpp:167:59: warning: bad option '-f avx2' to attribute 'optimize' [-Wattributes]
toll.cpp:167:59: warning: bad option '-f fma' to attribute 'optimize' [-Wattributes]
toll.cpp:198:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(register int i=0; i<EE.size(); i++) E[i+1]=EE[i];
| ~^~~~~~~~~~
toll.cpp:207:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for(register int i=0; i<VV.size(); i++)
| ~^~~~~~~~~~
toll.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%d%d%d", &N, &M, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:120:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
120 | for(register int i=1; i<=M; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:121:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | for(register int i=0; i<K; i++) scanf("%d%d", &A[i].first, &A[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:122:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
122 | for(register int i=1; i<=N; i++) scanf("%d", &B[i]);
| ~~~~~^~~~~~~~~~~~~
