Submission #235591

#	Time	Username	Problem	Language	Result	Execution time	Memory
235591		LittleFlowers__	Toll (APIO13_toll)	C++17	0 / 100	5 ms	384 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=1010;

int n,m,k,st,ed,ret,mx,ct;
int c[N],id[N];
struct pack{
    int u,v,c,nw;
};
vector<pack> E;
vector<ii> ad[N];
vector<int> val;

int root(int x){
    return !id[x]? x:id[x]=root(id[x]);
}
int join(int x,int y){
    if((x=root(x))==(y=root(y))) return 0;
    id[y]=x;
    return 1;
}

int dfs(int u,int p=0){
    int sz=c[u];
    forv(v,ad[u]) if(v.fi!=p){
        int tmp=dfs(v.fi,u);
        if(v.se) ct=tmp;
        sz+=tmp;
    }
    return sz;
}

int chk(int we){
    E.pb({st,ed,we,1});
    sort(all(E),[](pack i,pack j){
       return i.c<j.c || i.c==j.c && i.nw>j.nw;
    });
    int tot=0;
    reset(id,0);
    forinc(i,1,n) ad[i].clear();
    forv(i,E) if(join(i.u,i.v))
        ad[i.u].pb({i.v,i.nw}),
        ad[i.v].pb({i.u,i.nw}),
        tot+=i.c;
    if(tot>mx)
        return 0;
    dfs(1);
    forinc(i,0,E.size()-1)
        if(E[i].nw){
            swap(E[i],E.back());
            E.pop_back();
            return ct*we;
        }
}

main(){
    #define task "TOLL"
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);
    n=in,m=in,k=in;
    if(k>1) return -1;
    forinc(i,1,m){
        int u=in,v=in,c=in;
        E.pb({u,v,c});
    }
    st=in,ed=in;
    forinc(i,1,n) c[i]=in;
    sort(all(E),[](pack i,pack j){
       return i.c<j.c;
    });
    forv(i,E) if(join(i.u,i.v)) val.pb(i.c), val.pb(i.c-1), mx+=i.c;
    forv(i,val) ret=max(ret,chk(i));
    cout<<ret;
}

Compilation message (stderr)

toll.cpp: In lambda function:
toll.cpp:55:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        return i.c<j.c || i.c==j.c && i.nw>j.nw;
                          ~~~~~~~~~^~~~~~~~~~~~
toll.cpp: At global scope:
toll.cpp:75:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
toll.cpp: In function 'int chk(int)':
toll.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22