제출 #248507

#제출 시각아이디문제언어결과실행 시간메모리
248507sealnot123통행료 (APIO13_toll)C++14
100 / 100
1990 ms15712 KiB
#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()) 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 = 100005, M = 300005, K = 50; int n, m, k; vector<int> g[N]; int comp[N], n_comp; // tuple sucks vector< pair<int, PII> > all_edge; vector< PII > K_edge; int MST[M], dsu[N], MUST[M]; vector<int> try_edge; LL people[N], small_people[K+5]; int find(int i){ if(i == dsu[i]) return i; return dsu[i] = find(dsu[i]); } void dfs(int u = 1, int p = 1){ small_people[comp[u]] += people[u]; for(int e : g[u]){ if(abs(e) == p) continue; if(e < 0){ e = -e; comp[e] = ++n_comp; }else{ comp[e] = comp[u]; } dfs(e, u); } } vector<PII> small_g[K+5]; int Max[K+5], edge_idx[K+5]; int parent[K+5], depth[K+5]; int not_choose[K+5]; LL dp_people[K+5]; void make_parent(int u=1, int p=1){ dp_people[u] = small_people[u]; for(PII &e : small_g[u]){ if(e.x == p) continue; //printf("(%d, %d)\n",u,e.x); parent[e.x] = u; depth[e.x] = depth[u]+1; edge_idx[e.x] = e.y; make_parent(e.x, u); dp_people[u] += dp_people[e.x]; } } void play(LL &ans){ //puts("play reached"); for(int e : try_edge){ auto &f = all_edge[e].y; f.x = comp[f.x]; f.y = comp[f.y]; //assert(f.x != f.y); } for(PII &e : K_edge){ e.x = comp[e.x]; e.y = comp[e.y]; //assert(e.x != e.y); } edge_idx[1] = -1; FOR(mask, 1, (1<<k)-1){ memset(not_choose, 0, sizeof not_choose); FOR(i, 1, n_comp) dsu[i] = i, Max[i] = (1<<30); FOR(i, 0, k-1){ if(mask & (1<<i)){ PII &e = K_edge[i]; //printf("xx(%d, %d)",e.x,e.y); if(find(e.x) != find(e.y)){ //printf("add (%d, %d)\n",e.x,e.y); dsu[find(e.x)] = find(e.y); small_g[e.x].pb(PII(e.y, i)); small_g[e.y].pb(PII(e.x, i)); } } } //puts("===="); FOR(i, 0, SZ(try_edge)-1){ PII &e = all_edge[try_edge[i]].y; //printf("try (%d, %d)\n",e.x,e.y); if(find(e.x) != find(e.y)){ dsu[find(e.x)] = find(e.y); //printf("add (%d, %d)\n",e.x,e.y); small_g[e.x].pb(PII(e.y, -1)); small_g[e.y].pb(PII(e.x, -1)); }else{ not_choose[i] = 1; } } make_parent(); FOR(i, 0, SZ(try_edge)-1){ if(not_choose[i] == 0) continue; PII &e = all_edge[try_edge[i]].y; int v = all_edge[try_edge[i]].x; int a = e.x, b = e.y; //printf("(%d, %d) v = %d\n",a,b,v); while(a != b){ if(depth[a] < depth[b]) swap(a,b); Max[a] = min(Max[a], v); //printf("move %d -- %d\n",Max[a]); a = parent[a]; } } LL sum = 0; //FOR(i, 1, n_comp) printf("{%lld} ",dp_people[i]); puts(""); FOR(i, 1, n_comp){ if(edge_idx[i] >= 0) sum += dp_people[i] * Max[i]; small_g[i].clear(); } //printf("sum = %lld\n",sum); ans = max(ans, sum); } } void solve(){ scanf("%d %d %d",&n,&m,&k); FOR(i, 1, m){ int a, b, c; scanf("%d %d %d",&a,&b,&c); all_edge.pb({c,PII(a,b)}); } sort(all(all_edge)); FOR(i, 1, n) dsu[i] = i; FOR(i,0,SZ(all_edge)-1){ auto &e = all_edge[i]; int a = e.y.x, b = e.y.y; if(find(a) != find(b)){ MST[i] = 1; dsu[find(a)] = find(b); } } FOR(i,1,k){ int a, b; scanf("%d %d",&a,&b); K_edge.pb(PII(a,b)); } FOR(i,1,n) scanf("%lld",&people[i]); //puts("input success"); FOR(i, 1, n) dsu[i] = i; FOR(i, 0, SZ(K_edge)-1){ auto &e = K_edge[i]; if(find(e.x) != find(e.y)){ dsu[find(e.x)] = find(e.y); g[e.x].pb(-e.y); g[e.y].pb(-e.x); } } FOR(i, 0, SZ(all_edge)-1){ auto &e = all_edge[i]; int a = e.y.x, b = e.y.y; if(find(a) != find(b)){ MUST[i] = 1; dsu[find(a)] = find(b); g[a].pb(b); g[b].pb(a); } } //puts("Obtain MUST edges"); comp[1] = ++n_comp; dfs(); //puts("Generate component + small people success"); //printf("comp : "); FOR(i,1,n) printf("%d ",comp[i]); puts(""); FOR(i, 0, SZ(all_edge)-1){ if(MST[i] && MUST[i] == 0) try_edge.pb(i); } LL ans = 0; play(ans); printf("%lld",ans); } int main(){ solve(); return 0; } /* * * * * * * * * * * */

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'void solve()':
toll.cpp:134: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:137: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:152: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:155:21: 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 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...