## Submission #4575

# Submission time Handle Problem Language Result Execution time Memory
4575 2013-11-03T14:41:01 Z cki86201 Toll (APIO13_toll) C++
100 / 100
1408 ms 102596 KB
```#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;

#define Me(x) memset(x,0,sizeof(x))

// O( 2^K*K^2 + M);
const int MV = 100010;
const int ME = 600060;

int N,M,K;
struct UF{
int p[MV],mem[MV];
void init(int x){for(int i=1;i<=x;i++)p[i]=i,mem[i]=1;}
int Find(int x){
while(x!=p[x])x=p[x];
return x;
}
bool Union(int x,int y){
x=Find(x),y=Find(y);
if(x==y)return false;
if(mem[x]>mem[y])p[y]=x;
else p[x]=y;
if(mem[x]==mem[y])mem[y]++;
return true;
}
}uf;

struct Graph{
int st[MV], en[ME], len[ME], next[ME];
int c;
Graph(){c=1;}
void init(int x){for(int i=1;i<=x;i++)st[i]=0;c=1;}
inline void addedge(int s,int d,int l){++c,next[c]=st[s],st[s]=c,en[c]=d,len[c]=l;}
}I,MST;

struct LittleGraph{
int st[22], en[45], len[45], next[45];
int c;
LittleGraph(){c=1;}
void init(){Me(st),c=1;}
inline void addedge(int s,int d,int l){++c,next[c]=st[s],st[s]=c,en[c]=d,len[c]=l;}
int getmax(int s,int d){
int Q[22],i,fr=1,re=0,pre[22],ret=-1;
bool chk[22];
Me(chk);
Q[0]=s,chk[s]=1;
while(fr>re){
for(i=st[Q[re++]];i;i=next[i]){
int t=en[i];
if(chk[t])continue;
Q[fr++]=t;
chk[t]=1;
pre[t]=i;
if(t==d){
int tmp=d;
while(tmp!=s){
int u=pre[tmp];
if(ret<len[u])ret=len[u];
tmp=en[u^1];
}
return ret;
}
}
}
}
}T[1<<17],GR;

int inp[MV];
int gro[MV];
ll wi[23];
int Ka;
int sor[1000010];
ll ans;
bool cut[MV<<1];
bool check[MV];
ll wei[23];
bool chk[23];

void make_mst()
{
uf.init(N);
int i;
for(i=1;i<=1000000;i++){
if(sor[i]){
int x=I.en[sor[i]<<1],y=I.en[sor[i]<<1|1];
if(uf.Union(x,y)){
}
}
}
}

void dfs(int x,int c)
{
gro[x]=c;
wi[c]+=inp[x];
check[x]=1;
for(int i=MST.st[x];i;i=MST.next[i]){
if(!check[MST.en[i]]&&!cut[i])dfs(MST.en[i],c);
}
}

void make_mst2()
{
uf.init(N);
int i;
for(i=1;i<N;i++){
if(!uf.Union(MST.en[i<<1],MST.en[i<<1|1]))cut[i<<1]=cut[i<<1|1]=1;
}
for(i=1;i<=N;i++)if(!check[i])dfs(i,++Ka);
}

int getInt()
{
ABC:
int a=0;
char c=getchar();
while(isdigit(c)){
a=(a<<3)+(a<<1)+c-'0';
c=getchar();
}
if(a==0)goto ABC;
return a;
}

ll getans(int a,int x)
{
chk[x]=1;
ll ret=0;
for(int i=T[a].st[x];i;i=T[a].next[i]){
if(chk[T[a].en[i]])continue;
int d=T[a].en[i];
ret+=getans(a,d);
wei[x]+=wei[d];
if(T[a].len[i]<0)ret+=wei[d]*(-T[a].len[i]);
}
wei[x]+=wi[x];
return ret;
}

void bfs(int a,int s,int d,int l,int ver)
{
int Q[22],pre[22],fr=1,re=0,i;
Me(chk);
Q[0]=s;
chk[s]=1;
while(fr>re){
for(i=T[a].st[Q[re++]];i;i=T[a].next[i]){
int t=T[a].en[i];
if(chk[t])continue;
Q[fr++]=t;
chk[t]=1;
pre[t]=i;
if(t==d){
int tmp=t;
while(tmp!=s){
int u=pre[tmp];
if(ver && T[a].len[u] == -1e8)T[a].len[u]=T[a].len[u^1]=-l;
if(!ver && T[a].len[u]<0){
T[a].len[u]=T[a].len[u^1]=max(-l,T[a].len[u]);
}
tmp=T[a].en[u^1];
}
return;
}
}
}
}

ll solve(int x)
{
int a=0;
while((x&(1<<a))==0)a++;
int t=x-(1<<a);
if(m<=0)return -1;
int s,d;
for(int i=1;i<Ka;i++){
if(T[t].len[i<<1] == m)s=T[t].en[i<<1],d=T[t].en[i<<1|1];
}
bfs(x,s,d,m,0);
Me(chk),Me(wei);
return getans(x,1);
}

ll put(int x)
{
uf.init(Ka);
int i;
for(i=0;i<K-17;i++){
if(x&(1<<i)){
}
}
for(i=1;i<Ka;i++){
int x=GR.en[i<<1],y=GR.en[i<<1|1];
else bfs(0,x,y,GR.len[i<<1],1);
}
Me(chk),Me(wei);
return getans(0,1);
}

void Init()
{
for(int i=0;i<(1<<17);i++)T[i].init();
}

int main()
{
N=getInt(),M=getInt(),K=getInt();
int i;
for(i=1;i<=M;i++){
int x=getInt(),y=getInt(),z=getInt();
sor[z]=i;
}
for(i=1;i<=N;i++)inp[i]=getInt();
make_mst();
make_mst2();
for(i=0;i<(1<<K);i++){
if(i%(1<<17)==0){
Init();
ll a=put(i>>17);
ans=max(ans,a);
}
else{
ll a=solve((i%(1<<17)));
ans=max(ans,a);
}
}
printf("%lld",ans);
return 0;
}
```

#### Subtask #1 16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 102596 KB Output is correct
2 Correct 8 ms 102596 KB Output is correct

#### Subtask #2 18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 102596 KB Output is correct
2 Correct 4 ms 102596 KB Output is correct

#### Subtask #3 22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 102596 KB Output is correct
2 Correct 4 ms 102596 KB Output is correct

#### Subtask #4 22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 102596 KB Output is correct
2 Correct 172 ms 102596 KB Output is correct
3 Correct 164 ms 102596 KB Output is correct

#### Subtask #5 22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 102596 KB Output is correct
2 Correct 1336 ms 102596 KB Output is correct
3 Correct 1408 ms 102596 KB Output is correct