| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 73930 |
2018-08-29T09:38:03 Z |
ainta |
Toll (APIO13_toll) |
C++17 |
|
2330 ms |
19180 KB |
#include<stdio.h>
#include<algorithm>
#include<list>
#define N_ 101000
#define LIT list<Edge3>::iterator
using namespace std;
int N, M, K, Renum[N_], C, P[N_];
long long SZ[30], Res;
struct Edge{
int a, b, c;
bool operator <(const Edge &p)const{
return c < p.c;
}
}Ed[301000];
struct Edge2{
int a, b;
}w[30];
struct Edge3{
int a, b, gap;
bool ck;
}tp, par2[N_], def_E[30];
list <Edge3> E[N_];
int par[N_];
int find(int a){
if (a == par[a])return a;
return par[a] = find(par[a]);
}
void init(){
int i, x, y;
for (i = 1; i <= N; i++){
par[i] = i;
}
for (i = 0; i < M; i++){
x = find(Ed[i].a), y = find(Ed[i].b);
if (x == y)continue;
par[x] = y;
tp.a = Ed[i].a, tp.b = Ed[i].b, tp.gap = Ed[i].c, tp.ck = false;
E[Ed[i].a].push_back(tp);
tp.a = Ed[i].b, tp.b = Ed[i].a;
E[Ed[i].b].push_back(tp);
}
}
int Q[N_];
void BFS(int a){
int h = 0, t = 0, x;
LIT it;
Q[++t] = a, par2[a].a = a;
while (h < t){
x = Q[++h];
for (it = E[x].begin(); it!=E[x].end(); it++){
if (!par2[it->b].a){
Q[++t] =it->b;
par2[it->b] = *it;
}
}
}
}
int cnt;
void Modify(int a, int b, int c){
LIT it;
for (it = E[a].begin(); it!=E[a].end(); it++){
if (it->b == b){
if (c == -1){
E[a].erase(it);
break;
}
else it->gap = c;
}
}
}
void DFS(int a){
LIT it;
Renum[a] = C;
SZ[C] = SZ[C] + P[a];
for (it = E[a].begin(); it != E[a].end(); it++){
if (!(it->ck) && !Renum[it->b]){
DFS(it->b);
}
}
}
void Make_Compress(){
int i, x, y;
for (i = 1; i <= N; i++){
if (!Renum[i]){
C++;
DFS(i);
}
}
for (i = 1; i <= N; i++)E[i].clear();
for (i = 0; i < cnt; i++){
x = Renum[def_E[i].a], y = Renum[def_E[i].b];
tp.a = x, tp.b = y, tp.ck = false, tp.gap = def_E[i].gap;
E[x].push_back(tp);
tp.a = y, tp.b = x;
E[y].push_back(tp);
}
N = C;
}
long long DP[30], Sum;
void DFS2(int a){
DP[a] += SZ[a];
LIT it;
for (it = E[a].begin(); it != E[a].end(); it++){
if (DP[it->b])continue;
DFS2(it->b);
if (it->ck){
Sum += DP[it->b] * (long long)it->gap;
}
DP[a] += DP[it->b];
}
return;
}
long long Calc()
{
int i;
for (i = 1; i <= N; i++)DP[i] = 0;
Sum = 0;
DFS2(1);
return Sum;
}
void Make_MST(int a, bool ck){
if (a == K){
if (!ck) Make_Compress();
else{
long long t = Calc();
if (Res < t)Res = t;
}
return;
}
if (ck)Make_MST(a + 1, ck);
int i, x = w[a].a, y = w[a].b, Max = -1, ma, mb, ty, cc=0;
Edge3 TP[22];
if (ck)x = Renum[x], y = Renum[y];
ty = y;
for (i = 1; i <= N; i++){
par2[i].a = 0;
}
BFS(x);
while (y != x){
if (!par2[y].ck && Max < par2[y].gap){
ma = y, mb = par2[y].a, Max = par2[y].gap;
}
y = par2[y].a;
}
if (Max == -1){
Make_MST(a + 1, ck);
return;
}
if(!ck) def_E[cnt].a = ma, def_E[cnt].b = mb, def_E[cnt++].gap = Max;
Modify(ma, mb, -1);
Modify(mb, ma, -1);
y = ty;
tp.a = x, tp.b = y, tp.gap = Max, tp.ck = true;
E[x].push_back(tp);
tp.a = y, tp.b = x;
E[y].push_back(tp);
while (y != x){
if (par2[y].ck && Max < par2[y].gap){
TP[cc++] = par2[y];
Modify(y, par2[y].a, Max);
Modify(par2[y].a, y, Max);
}
y = par2[y].a;
}
Make_MST(a + 1, ck);
if (!ck)return;
y = ty;
Modify(x, y, -1);
Modify(y, x, -1);
tp.a = ma, tp.b = mb, tp.gap = Max, tp.ck = false;
E[ma].push_back(tp);
tp.a = mb, tp.b = ma;
E[mb].push_back(tp);
for (i = 0; i < cc; i++){
Modify(TP[i].a, TP[i].b, TP[i].gap);
Modify(TP[i].b, TP[i].a, TP[i].gap);
}
}
int main()
{
int i;
scanf("%d%d%d", &N, &M, &K);
for (i = 0; i < M; i++){
scanf("%d%d%d", &Ed[i].a, &Ed[i].b, &Ed[i].c);
}
sort(Ed, Ed + M);
for (i = 0; i < K; i++){
scanf("%d%d", &w[i].a, &w[i].b);
}
for (i = 1; i <= N; i++){
scanf("%d", &P[i]);
}
init();
Make_MST(0, 0);
Make_MST(0, 1);
printf("%lld\n", Res);
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:195: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:197:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &Ed[i].a, &Ed[i].b, &Ed[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:201:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &w[i].a, &w[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:204:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &P[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2792 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2792 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2792 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2792 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2792 KB |
Output is correct |
| 5 |
Correct |
12 ms |
2976 KB |
Output is correct |
| 6 |
Correct |
12 ms |
3052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2792 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2792 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2792 KB |
Output is correct |
| 5 |
Correct |
12 ms |
2976 KB |
Output is correct |
| 6 |
Correct |
12 ms |
3052 KB |
Output is correct |
| 7 |
Correct |
954 ms |
19104 KB |
Output is correct |
| 8 |
Correct |
904 ms |
19104 KB |
Output is correct |
| 9 |
Correct |
873 ms |
19156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2792 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2792 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2792 KB |
Output is correct |
| 5 |
Correct |
12 ms |
2976 KB |
Output is correct |
| 6 |
Correct |
12 ms |
3052 KB |
Output is correct |
| 7 |
Correct |
954 ms |
19104 KB |
Output is correct |
| 8 |
Correct |
904 ms |
19104 KB |
Output is correct |
| 9 |
Correct |
873 ms |
19156 KB |
Output is correct |
| 10 |
Correct |
1819 ms |
19156 KB |
Output is correct |
| 11 |
Correct |
2176 ms |
19172 KB |
Output is correct |
| 12 |
Correct |
2330 ms |
19180 KB |
Output is correct |
