| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 351692 |
2021-01-20T06:39:50 Z |
arnold518 |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
16224 KB |
#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];
int B[MAXN+10];
struct UF
{
int par[MAXN+10];
vector<int> V[MAXN+10];
void init()
{
for(int i=1; i<=N; i++)
{
par[i]=i;
V[i].clear();
}
}
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(V[x].size()>V[y].size()) swap(x, y);
for(auto it : V[x]) V[y].push_back(it);
par[x]=y; V[x].clear();
}
}uf;
ll ans, val=0;
vector<pii> adj[MAXN+10];
ll sz[MAXN+10];
vector<int> ST;
int P[MAXK+10];
void dfs(int now, int bef, int k)
{
sz[now]=B[now];
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
int t=0;
if(nxt.second!=-1) t=P[nxt.second];
dfs(nxt.first, now, t);
sz[now]+=sz[nxt.first];
}
//printf("?%d : %d\n", now, sz[now]);
val+=sz[now]*k;
}
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 main()
{
scanf("%d%d%d", &N, &M, &K);
for(int i=1; i<=M; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
for(int i=0; i<K; i++) scanf("%d%d", &A[i].first, &A[i].second);
for(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(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(int i=0; i<EE.size(); i++) E[i+1]=EE[i];
M=EE.size();
assert(M==N-1);
for(int i=0; i<(1<<K); i++)
{
vector<int> V;
for(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(int i=1; i<=N; i++) adj[i].clear();
continue;
}
for(int j=0; j<K; j++) P[j]=0;
for(int j=1; j<=M; j++)
{
if(uf.Find(E[j].u)==uf.Find(E[j].v))
{
ST.clear();
dfs2(E[j].u, E[j].u, E[j].v);
for(auto it : ST) P[it]=E[j].w;
}
else
{
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);
}
}
val=0;
dfs(1, 1, 0);
ans=max(ans, val);
for(int i=1; i<=N; i++) adj[i].clear();
}
printf("%lld\n", ans);
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=0; i<EE.size(); i++) E[i+1]=EE[i];
| ~^~~~~~~~~~
toll.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | scanf("%d%d%d", &N, &M, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:87:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
87 | for(int i=1; i<=M; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:88:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
88 | for(int i=0; i<K; i++) scanf("%d%d", &A[i].first, &A[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:89:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
89 | for(int i=1; i<=N; i++) scanf("%d", &B[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4972 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4972 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
109 ms |
5228 KB |
Output is correct |
| 6 |
Correct |
47 ms |
5228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4972 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
109 ms |
5228 KB |
Output is correct |
| 6 |
Correct |
47 ms |
5228 KB |
Output is correct |
| 7 |
Execution timed out |
2575 ms |
16224 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4972 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4972 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
109 ms |
5228 KB |
Output is correct |
| 6 |
Correct |
47 ms |
5228 KB |
Output is correct |
| 7 |
Execution timed out |
2575 ms |
16224 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
