Submission #562043

#TimeUsernameProblemLanguageResultExecution timeMemory
562043fcmalkcinToll (APIO13_toll)C++17
0 / 100
1 ms1108 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=1e5+10; const ll maxn1=1e5+10; const ll mod=1e9+7 ; const ll base=3e18; /// i believe myself /// goal 2/7 ll par[maxn]; ll find_par(ll u) { if (par[u]<0) return u; return par[u]=find_par(par[u]); } bool dsu(ll x,ll y) { x=find_par(x); y=find_par(y); if (x==y) return false; if (par[x]>par[y]) swap(x,y); par[x]+=par[y]; par[y]=x; return true; } ll x[23]; ll y[23]; ll p[maxn]; ll id[maxn]; ll val[23]; vector<pll> adj[23]; bool chk1[23]; ll siz[23]; ll anc[23]; ll dep[23]; ll mx[23]; void dfs(ll u,ll par) { anc[u]=par; siz[u]=val[u]; for (auto p:adj[u]) { ll to=p.ff; if (to==par) continue; dep[to]=dep[u]+1; dfs(to,u); siz[u]+=siz[to]; } } /* 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 */ int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ll n, m, k; cin>> n>> m>> k; vector<pair<ll,pll>> vt; vector<pair<ll,pll>> vt1,vt3; for (int i=1;i<=m;i++) { ll x, y, w; cin>> x>> y>> w; vt.pb(make_pair(w,make_pair(x,y))); } memset(par,-1,sizeof(par)); for (int t=0;t<k;t++) { cin>> x[t]>>y[t]; dsu(x[t],y[t]); } for (int i=1;i<=n;i++) { cin>> p[i]; } sort(vt.begin(),vt.end()); vector<pll> vt2; for (auto to:vt) { auto p=to.ss; if (dsu(p.ff,p.ss)) { vt2.pb(p); } else { vt1.pb(to); } } memset(par,-1,sizeof(par)); for (auto to:vt2) { dsu(to.ff,to.ss); } for (auto to:vt1) { if (dsu(to.ss.ff,to.ss.ss)) { vt3.pb(to); } } memset(par,-1,sizeof(par)); for (auto to:vt2) { dsu(to.ff,to.ss); } ll cntn=0; for (int i=1;i<=n;i++) { if (i==find_par(i)) { id[i]=cntn; cntn++; } } for (int i=1;i<=n;i++) { val[id[find_par(i)]]+=p[i]; } ll rt=id[find_par(1)]; for (int i=0;i<k;i++) { x[i]=id[find_par(x[i])]; y[i]=id[find_par(y[i])]; } for (int i=0;i<vt3.size();i++) { vt3[i].ss.ff=id[find_par(vt3[i].ss.ff)]; vt3[i].ss.ss=id[find_par(vt3[i].ss.ss)]; } n=cntn; m=vt3.size(); ll res=0; for (int t=0;t<(1ll<<k);t++) { for (int p=0;p<n;p++) par[p]=-1,mx[p]=base; bool chk=true; for (int i=0;i<k;i++) { if (t&(1ll<<i)) { if (dsu(x[i],y[i])) { adj[x[i]].pb(make_pair(y[i],1)); adj[y[i]].pb(make_pair(x[i],1)); } else { chk=false; break; } } } if (!chk) continue; for (int i=0;i<m;i++) { auto p=vt3[i].ss; if (dsu(p.ff,p.ss)) { adj[p.ff].pb(make_pair(p.ss,0)); adj[p.ss].pb(make_pair(p.ff,0)); } else { chk1[i]=1; } } dfs(rt,0); for (int i=0;i<m;i++) { if (chk1[i]) { auto p=vt3[i].ss; ll u=p.ff; ll v=p.ss; while (u!=v) { if (dep[u]<dep[v]) swap(u,v); mx[u]=min(mx[u],vt3[i].ff); u=anc[u]; } } chk1[i]=0; } ll ans=0; for (int i=0;i<n;i++) { for (auto p:adj[i]) { if (p.ff==anc[i]||p.ss==0) continue; ans+=((siz[p.ff])*mx[p.ff]); } adj[i].clear(); } res=max(res,ans); } cout <<res<<endl; }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:155:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i=0;i<vt3.size();i++)
      |                  ~^~~~~~~~~~~
toll.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...