| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 247101 |
2020-07-11T05:35:37 Z |
sealnot123 |
Toll (APIO13_toll) |
C++14 |
|
8 ms |
768 KB |
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define iFOR(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())
#define mt make_tuple
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;
const int N = 33, K = 15;
LL people[N];
int mark[N+K], ans[N+K];
vector< tuple<int,int,int> > g[N], edge;
queue<int> bfs;
bool visit[N];
int level[N], wp[N], parent[N];
int n;
bool iterate(int total, int &CH){
memset(visit, 0, sizeof visit);
memset(parent, 0, sizeof parent);
memset(level, 0, sizeof level);
visit[1] = true;
bfs.push(1);
while(!bfs.empty()){
int u = bfs.front();
bfs.pop();
for(auto &e : g[u]){
int a, b ,c; // node, weight, address
tie(a, b, c) = e;
if(mark[c] == -1) continue;
if(parent[u] == a) continue;
if(visit[a]){
mark[c] = 0; continue;
}
visit[a] = true;
level[a] = level[u]+1;
parent[a] = u;
wp[a] = c;
mark[c] = 1;
bfs.push(a);
}
}
int cnt = 0;
FOR(i, 0, total-1){
int a, b, c; // node1, node2, weight
tie(a, b, c) = edge[i];
if(mark[i] != 0) continue;
++cnt;
// find max
int Max = c, x;
int aa = a, bb = b;
while(a != b){
if(level[a] < level[b]) swap(a,b);
if((x = get<2>(edge[wp[a]])) > 0){
Max = max(Max, x);
}
a = parent[a];
}
if(Max == -1){
CH = 0; return false;
}
ans[i] = min(ans[i], Max);
if(c == Max){
mark[i] = -1;
}
a = aa; b = bb;
while(a != b){
if(level[a] < level[b]) swap(a,b);
int x = get<2>(edge[wp[a]]);
int &y = ans[wp[a]];
y = min(y, Max);
if(x == Max) mark[wp[a]] = -1;
a = parent[a];
}
}
//printf("ans :"); FOR(i, 0, total-1) printf("%d ",ans[i]);
//puts("");
//printf("wp :"); FOR(i, 1, n) printf("%d ",wp[i]);
//puts("");
if(cnt != 0 ) return true;
return false;
}
LL dfs(int u, int p, LL &value){
LL sz = people[u];
for(auto &e : g[u]){
int a, b, c;
tie(a,b,c) = e;
if(a == p) continue;
if(mark[c] == -1) continue;
sz += dfs(a, u, value);
}
if(u != 1){
int a, b, c;
tie(a,b,c) = edge[wp[u]];
if(c == -1) value += sz * ans[wp[u]];
}
return sz;
}
LL play(int total){
memset(mark, 0, sizeof mark);
FOR(i, 1, n) g[i].clear();
FOR(i, 0, total-1) ans[i] = 1<<30;
FOR(i, 0, total-1){
int a, b, c;
tie(a, b, c) = edge[i];
//printf("Add edge : (%d,%d)\n",a,b);
g[a].pb(mt(b,c,i));
g[b].pb(mt(a,c,i));
}
int ch = 1;
while(iterate(total, ch));
if(ch == 0) return -1;
LL value = 0;
dfs(1,1,value);
return value;
}
int p[N];
int fin(int i){
if(i == p[i]) return i;
return p[i]=fin(p[i]);
}
vector<pair<int,PII>> edge_init;
vector<tuple<int,int,int>> edge_mst, edge_k;
int main(){
int m, k;
scanf("%d %d %d",&n,&m,&k);
FOR(i, 1, m){
int a, b, c;
scanf("%d %d %d",&a,&b,&c);
edge_init.pb( {c, PII(a, b)} );
}
sort(all(edge_init));
FOR(i, 1, n) p[i] = i;
for(auto &e : edge_init){
int a, b;
a = e.y.x; b = e.y.y;
if(fin(a) != fin(b)){
edge_mst.pb(mt(a, b, e.x));
//printf("(%d, %d) selected\n",a,b);
p[fin(a)] = fin(b);
}
}
FOR(i, 1, k){
int a, b;
scanf("%d %d",&a,&b);
edge_k.pb(mt(a, b, -1));
}
FOR(i, 1, n) scanf("%lld",&people[i]);
LL answer = 0;
FOR(i, 1, (1<<k)-1){
edge.clear();
edge = edge_mst;
FOR(j, 0, k-1){
if(i & (1<<j)){
edge.pb( edge_k[j] );
}
}
answer = max(answer, play(SZ(edge)));
}
printf("%lld",answer);
return 0;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:141: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:144:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&a,&b,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
~~~~~^~~~~~~~~~~~~~~
toll.cpp:163:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
FOR(i, 1, n) scanf("%lld",&people[i]);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
8 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
8 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
7 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
8 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
7 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
8 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
7 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
