Submission #1416777
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) typedef vector<int> vi; typedef pair<int,int> pii; int n,m,k; vector<pii> g[125]; int eid[125][125]; int cst[125][125]; int c2[12525]; pii edges[12525]; bool cycled[12525]; int data[125]; int root(int x){ return data[x]<0?x:data[x]=root(data[x]); } void unite(int a,int b){ a = root(a); b = root(b); if(a!=b){ if(data[a]>data[b])swap(a,b); data[a] += data[b]; data[b] = a; } } bool used[125]; deque<int> stk; bool dfs(int p,int bef){ stk.push_back(p); if(used[p]){ return true; } used[p] = true; for(pii to : g[p])if(to.first!=bef){ if(dfs(to.first,p)){ return true; } } used[p] = false; stk.pop_back(); return false; } int main(){ scanf("%d%d%d",&n,&m,&k); REP(i,n)data[i] = -1; REP(i,n)REP(j,n)eid[i][j] = -1; REP(i,m){ int f,t,c; scanf("%d%d%d",&f,&t,&c); --f;--t; unite(f,t); g[f].push_back(pii(t,c)); g[t].push_back(pii(f,c)); eid[f][t] = eid[t][f] = i; cst[f][t] = cst[t][f] = c; c2[i] = c; edges[i] = pii(c,i); } sort(edges,edges+m); REP(i,n)if(i==root(i))k--; // cycle REP(i,n)if(i==root(i)){ if(dfs(i,-1)){ // cycle int cyclebegin = stk.back(); while(stk.front() != cyclebegin){ stk.pop_front(); } stk.pop_front(); break; } } int ans = 1252183025; if(stk.size() > 0){ // cycle int cid = -1; REP(i,stk.size()){ int s = stk[i]; int t = stk[(i+1)%stk.size()]; int id = eid[s][t]; if(cid==-1 || c2[cid] > c2[id]){ cid = id; } cycled[id] = true; } int tmp = c2[cid]; int x = k; REP(i,m){ if(x<=0)break; if(edges[i].second == cid)continue; x--; tmp += edges[i].first; } ans = min(ans,tmp); } { int tmp = 0; int x = k; REP(i,m){ if(x<=0)break; int id = edges[i].second; if(cycled[id])continue; x--; tmp += edges[i].first; } if(x<=0)ans = min(ans,tmp); } printf("%d\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 独立記念日 |
User | rickytheta |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2230 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 384 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:49:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&n,&m,&k); ^ ./Main.cpp:54:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&f,&t,&c); ^
Judge Result
Set Name | nonloop | loop | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 70 / 70 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
nonloop | nonloop/case_000.txt, nonloop/case_001.txt, nonloop/case_002.txt, nonloop/case_003.txt, nonloop/case_004.txt, nonloop/case_005.txt, nonloop/case_006.txt, nonloop/case_007.txt, nonloop/case_008.txt, nonloop/case_009.txt, nonloop/case_010.txt, nonloop/case_011.txt, nonloop/case_012.txt, nonloop/case_013.txt, nonloop/case_014.txt, nonloop/case_015.txt, nonloop/case_016.txt, nonloop/case_017.txt, nonloop/case_018.txt, nonloop/case_019.txt, nonloop/case_020.txt, nonloop/case_021.txt, nonloop/case_022.txt, nonloop/case_023.txt, nonloop/case_024.txt, nonloop/case_025.txt, nonloop/case_026.txt, nonloop/case_027.txt, nonloop/case_028.txt, nonloop/case_029.txt, nonloop/case_030.txt, nonloop/case_031.txt, nonloop/case_032.txt, nonloop/case_033.txt |
loop | loop/case_000.txt, loop/case_001.txt, loop/case_002.txt, loop/case_003.txt, loop/case_004.txt, loop/case_005.txt, loop/case_006.txt, loop/case_007.txt, loop/case_008.txt, loop/case_009.txt, loop/case_010.txt, loop/case_011.txt, loop/case_012.txt, loop/case_013.txt, loop/case_014.txt, loop/case_015.txt, loop/case_016.txt, loop/case_017.txt, loop/case_018.txt, loop/case_019.txt, loop/case_020.txt, loop/case_021.txt, loop/case_022.txt, loop/case_023.txt, loop/case_024.txt, loop/case_025.txt, loop/case_026.txt, loop/case_027.txt, loop/case_028.txt, loop/case_029.txt, loop/case_030.txt, loop/case_031.txt, loop/case_032.txt, loop/case_033.txt, loop/loop_case_000.txt, loop/loop_case_001.txt, loop/loop_case_002.txt, loop/loop_case_003.txt, loop/loop_case_004.txt, loop/loop_case_005.txt, loop/loop_case_006.txt, loop/loop_case_007.txt, loop/loop_case_008.txt, loop/loop_case_009.txt, loop/loop_case_010.txt, loop/loop_case_011.txt, loop/loop_case_012.txt, loop/loop_case_013.txt, loop/loop_case_014.txt, loop/loop_case_015.txt, loop/loop_case_016.txt, loop/loop_case_017.txt, loop/loop_case_018.txt, loop/loop_case_019.txt, loop/loop_case_020.txt, loop/loop_case_021.txt, loop/loop_case_022.txt, loop/loop_case_023.txt, loop/loop_case_024.txt, loop/loop_case_025.txt, loop/loop_case_026.txt, loop/loop_case_027.txt, loop/loop_case_028.txt, loop/loop_case_029.txt, loop/loop_case_030.txt, loop/loop_case_031.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
loop/case_000.txt | AC | 1 ms | 256 KB |
loop/case_001.txt | AC | 1 ms | 256 KB |
loop/case_002.txt | AC | 1 ms | 256 KB |
loop/case_003.txt | AC | 1 ms | 256 KB |
loop/case_004.txt | AC | 1 ms | 256 KB |
loop/case_005.txt | AC | 1 ms | 256 KB |
loop/case_006.txt | AC | 1 ms | 256 KB |
loop/case_007.txt | AC | 1 ms | 256 KB |
loop/case_008.txt | AC | 1 ms | 256 KB |
loop/case_009.txt | AC | 1 ms | 256 KB |
loop/case_010.txt | AC | 1 ms | 256 KB |
loop/case_011.txt | AC | 1 ms | 256 KB |
loop/case_012.txt | AC | 1 ms | 256 KB |
loop/case_013.txt | AC | 1 ms | 256 KB |
loop/case_014.txt | AC | 1 ms | 384 KB |
loop/case_015.txt | AC | 1 ms | 384 KB |
loop/case_016.txt | AC | 1 ms | 384 KB |
loop/case_017.txt | AC | 1 ms | 384 KB |
loop/case_018.txt | AC | 1 ms | 384 KB |
loop/case_019.txt | AC | 1 ms | 256 KB |
loop/case_020.txt | AC | 1 ms | 384 KB |
loop/case_021.txt | AC | 1 ms | 384 KB |
loop/case_022.txt | AC | 1 ms | 256 KB |
loop/case_023.txt | AC | 1 ms | 384 KB |
loop/case_024.txt | AC | 1 ms | 256 KB |
loop/case_025.txt | AC | 1 ms | 384 KB |
loop/case_026.txt | AC | 1 ms | 384 KB |
loop/case_027.txt | AC | 1 ms | 384 KB |
loop/case_028.txt | AC | 1 ms | 384 KB |
loop/case_029.txt | AC | 1 ms | 256 KB |
loop/case_030.txt | AC | 1 ms | 256 KB |
loop/case_031.txt | AC | 1 ms | 384 KB |
loop/case_032.txt | AC | 1 ms | 384 KB |
loop/case_033.txt | AC | 1 ms | 384 KB |
loop/loop_case_000.txt | AC | 1 ms | 256 KB |
loop/loop_case_001.txt | AC | 1 ms | 256 KB |
loop/loop_case_002.txt | AC | 1 ms | 256 KB |
loop/loop_case_003.txt | AC | 1 ms | 256 KB |
loop/loop_case_004.txt | AC | 1 ms | 256 KB |
loop/loop_case_005.txt | AC | 1 ms | 256 KB |
loop/loop_case_006.txt | AC | 1 ms | 256 KB |
loop/loop_case_007.txt | AC | 1 ms | 256 KB |
loop/loop_case_008.txt | AC | 1 ms | 256 KB |
loop/loop_case_009.txt | AC | 1 ms | 256 KB |
loop/loop_case_010.txt | AC | 1 ms | 256 KB |
loop/loop_case_011.txt | AC | 1 ms | 256 KB |
loop/loop_case_012.txt | AC | 1 ms | 384 KB |
loop/loop_case_013.txt | AC | 1 ms | 384 KB |
loop/loop_case_014.txt | AC | 1 ms | 384 KB |
loop/loop_case_015.txt | AC | 1 ms | 384 KB |
loop/loop_case_016.txt | AC | 1 ms | 384 KB |
loop/loop_case_017.txt | AC | 1 ms | 384 KB |
loop/loop_case_018.txt | AC | 1 ms | 384 KB |
loop/loop_case_019.txt | AC | 1 ms | 384 KB |
loop/loop_case_020.txt | AC | 1 ms | 384 KB |
loop/loop_case_021.txt | AC | 1 ms | 384 KB |
loop/loop_case_022.txt | AC | 1 ms | 384 KB |
loop/loop_case_023.txt | AC | 1 ms | 384 KB |
loop/loop_case_024.txt | AC | 1 ms | 256 KB |
loop/loop_case_025.txt | AC | 1 ms | 384 KB |
loop/loop_case_026.txt | AC | 1 ms | 384 KB |
loop/loop_case_027.txt | AC | 1 ms | 384 KB |
loop/loop_case_028.txt | AC | 1 ms | 384 KB |
loop/loop_case_029.txt | AC | 1 ms | 384 KB |
loop/loop_case_030.txt | AC | 1 ms | 384 KB |
loop/loop_case_031.txt | AC | 1 ms | 384 KB |
nonloop/case_000.txt | AC | 1 ms | 256 KB |
nonloop/case_001.txt | AC | 1 ms | 256 KB |
nonloop/case_002.txt | AC | 1 ms | 256 KB |
nonloop/case_003.txt | AC | 1 ms | 256 KB |
nonloop/case_004.txt | AC | 1 ms | 256 KB |
nonloop/case_005.txt | AC | 1 ms | 256 KB |
nonloop/case_006.txt | AC | 1 ms | 256 KB |
nonloop/case_007.txt | AC | 1 ms | 256 KB |
nonloop/case_008.txt | AC | 1 ms | 256 KB |
nonloop/case_009.txt | AC | 1 ms | 256 KB |
nonloop/case_010.txt | AC | 1 ms | 256 KB |
nonloop/case_011.txt | AC | 1 ms | 256 KB |
nonloop/case_012.txt | AC | 1 ms | 256 KB |
nonloop/case_013.txt | AC | 1 ms | 256 KB |
nonloop/case_014.txt | AC | 1 ms | 384 KB |
nonloop/case_015.txt | AC | 1 ms | 384 KB |
nonloop/case_016.txt | AC | 1 ms | 384 KB |
nonloop/case_017.txt | AC | 1 ms | 384 KB |
nonloop/case_018.txt | AC | 1 ms | 384 KB |
nonloop/case_019.txt | AC | 1 ms | 256 KB |
nonloop/case_020.txt | AC | 1 ms | 384 KB |
nonloop/case_021.txt | AC | 1 ms | 384 KB |
nonloop/case_022.txt | AC | 1 ms | 256 KB |
nonloop/case_023.txt | AC | 1 ms | 384 KB |
nonloop/case_024.txt | AC | 1 ms | 256 KB |
nonloop/case_025.txt | AC | 1 ms | 384 KB |
nonloop/case_026.txt | AC | 1 ms | 384 KB |
nonloop/case_027.txt | AC | 1 ms | 384 KB |
nonloop/case_028.txt | AC | 1 ms | 384 KB |
nonloop/case_029.txt | AC | 1 ms | 256 KB |
nonloop/case_030.txt | AC | 1 ms | 256 KB |
nonloop/case_031.txt | AC | 1 ms | 384 KB |
nonloop/case_032.txt | AC | 1 ms | 384 KB |
nonloop/case_033.txt | AC | 1 ms | 384 KB |