Submission #1369801
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(...) _dbg(#__VA_ARGS__",", __VA_ARGS__) void _dbg(string){cout<<endl;} template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);} template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;} template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;} #define INF 1120000000 struct edge{ int to, cost, id; }; vector<edge> vec[100]; bool visited[100]; pair<int,bool> es[10000]; // edge-id, is-heiro? int circle_from = -1; bool dfs(int d, int from){ visited[d]=true; bool iscircle=false; for(auto &e : vec[d]) if(e.to!=from){ if(visited[e.to]){ iscircle = true; es[e.id].se = true; circle_from = e.to; } else { if( dfs(e.to, d) ){ iscircle = true; es[e.id].se = true; } } } if(circle_from==d) iscircle=false; return iscircle; } int main(){ int n,m,k; cin>>n>>m>>k; rep(i,m){ int a,b,c; cin>>a>>b>>c; a--;b--; vec[a].pb(((edge){b,c,i})); vec[b].pb(((edge){a,c,i})); es[i] = mp(c,false); } fill(visited, visited+n, false); int s = 0; rep(i,n) if(!visited[i]){ s++; dfs(i,-1); } if(s>=k){ cout << 0 << endl; return 0; } sort(es, es+m); vector<int> heiro, eda; rep(i,m){ if(es[i].se) heiro.pb(es[i].fi); else eda.pb(es[i].fi); } sort(all(heiro)); sort(all(eda)); long ans = 12345678901234; if(eda.size()>=k-s){ long tmp = 0; rep(i,k-s) tmp+= eda[i]; ans = min(ans, tmp); } if(heiro.size()>0){ long tmp = heiro[0]; vector<int> hoge; hoge.resize(eda.size()+heiro.size()-1); merge(all(eda), ++begin(heiro), end(heiro), hoge.begin()); rep(i,k-s) tmp += hoge[i]; ans = min(ans, tmp); } assert(ans < INF); cout << ans << endl; // // int ans = INF; // if(k-s+1<=m){ // int tmp = 0; // rep(i,k-s+1) tmp += es[i].fi; // ans = min(tmp, ans); // } // { // int i=0; int cnt=0; int tmp=0; // while(i<m && cnt<k-s){ // if(es[i].se==false){cnt++; tmp+=es[i].fi;} // i++; // } // if(cnt==k-s) ans = min(ans, tmp); // } // cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 独立記念日 |
User | tossy |
Language | C++14 (GCC 5.4.1) |
Score | 30 |
Code Size | 2755 Byte |
Status | WA |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | nonloop | loop | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 0 / 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 | 256 KB |
loop/case_015.txt | AC | 1 ms | 256 KB |
loop/case_016.txt | AC | 1 ms | 256 KB |
loop/case_017.txt | AC | 1 ms | 256 KB |
loop/case_018.txt | AC | 1 ms | 256 KB |
loop/case_019.txt | AC | 1 ms | 256 KB |
loop/case_020.txt | AC | 1 ms | 256 KB |
loop/case_021.txt | AC | 1 ms | 256 KB |
loop/case_022.txt | AC | 1 ms | 256 KB |
loop/case_023.txt | AC | 1 ms | 256 KB |
loop/case_024.txt | AC | 1 ms | 256 KB |
loop/case_025.txt | AC | 1 ms | 256 KB |
loop/case_026.txt | AC | 1 ms | 256 KB |
loop/case_027.txt | AC | 1 ms | 256 KB |
loop/case_028.txt | AC | 1 ms | 256 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 | 256 KB |
loop/case_032.txt | AC | 1 ms | 256 KB |
loop/case_033.txt | AC | 1 ms | 256 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 | 256 KB |
loop/loop_case_013.txt | AC | 1 ms | 256 KB |
loop/loop_case_014.txt | AC | 1 ms | 256 KB |
loop/loop_case_015.txt | WA | 1 ms | 256 KB |
loop/loop_case_016.txt | AC | 1 ms | 256 KB |
loop/loop_case_017.txt | WA | 1 ms | 256 KB |
loop/loop_case_018.txt | AC | 1 ms | 256 KB |
loop/loop_case_019.txt | AC | 1 ms | 256 KB |
loop/loop_case_020.txt | AC | 1 ms | 256 KB |
loop/loop_case_021.txt | AC | 1 ms | 256 KB |
loop/loop_case_022.txt | AC | 1 ms | 256 KB |
loop/loop_case_023.txt | AC | 1 ms | 256 KB |
loop/loop_case_024.txt | WA | 1 ms | 256 KB |
loop/loop_case_025.txt | AC | 1 ms | 256 KB |
loop/loop_case_026.txt | AC | 1 ms | 256 KB |
loop/loop_case_027.txt | AC | 1 ms | 256 KB |
loop/loop_case_028.txt | WA | 1 ms | 256 KB |
loop/loop_case_029.txt | AC | 1 ms | 256 KB |
loop/loop_case_030.txt | AC | 1 ms | 256 KB |
loop/loop_case_031.txt | AC | 1 ms | 256 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 | 256 KB |
nonloop/case_015.txt | AC | 1 ms | 256 KB |
nonloop/case_016.txt | AC | 1 ms | 256 KB |
nonloop/case_017.txt | AC | 1 ms | 256 KB |
nonloop/case_018.txt | AC | 1 ms | 256 KB |
nonloop/case_019.txt | AC | 1 ms | 256 KB |
nonloop/case_020.txt | AC | 1 ms | 256 KB |
nonloop/case_021.txt | AC | 1 ms | 256 KB |
nonloop/case_022.txt | AC | 1 ms | 256 KB |
nonloop/case_023.txt | AC | 1 ms | 256 KB |
nonloop/case_024.txt | AC | 1 ms | 256 KB |
nonloop/case_025.txt | AC | 1 ms | 256 KB |
nonloop/case_026.txt | AC | 1 ms | 256 KB |
nonloop/case_027.txt | AC | 1 ms | 256 KB |
nonloop/case_028.txt | AC | 1 ms | 256 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 | 256 KB |
nonloop/case_032.txt | AC | 1 ms | 256 KB |
nonloop/case_033.txt | AC | 1 ms | 256 KB |