Submission #61583


Source Code Expand

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

const int INF = 1001001001;

vector<bool> visited;
vector<pii> C;
int dfs(vvi& G, int n, int src)
{
	if(visited[n])
		return n;
	visited[n] = true;
	
	rep(i, G[n].size()){
		if(src == i || G[n][i] == -1)
			continue;
		
		int ret = dfs(G, i, n);
		if(ret == -2) return -2;
		if(ret != -1){
			C.push_back(pii(min(n,i), max(n,i)));
			if(ret == n)
				return -2;
			else
				return ret;
		}
	}
	
	return -1;
}

void connect(vvi& G, int n){
	if(visited[n]) return;
	visited[n] = true;
	rep(i, G[n].size()){
		if(G[n][i] == -1)
			continue;
		connect(G, i);
	}
}

int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	
	vvi G(n, vi(n, -1));
	rep(i, m){
		int f, t, c;
		scanf("%d%d%d", &f, &t, &c);
		--f; --t;
		G[f][t] = c;
		G[t][f] = c;
	}
	
	visited.assign(n, false);
	int conn = 0;
	rep(i, n){
		if(!visited[i]){
			++conn;
			connect(G, i);
		}
	}
	k -= conn;
	if(k<=0){
		puts("0");
		return 0;
	}
	
	vi cycle, tree;
	rep(i, n){
		visited.assign(n, false);
		dfs(G, i, -1);
		if(!C.empty())
			break;
	}

	sort(C.begin(), C.end());
	rep(i, n) rep(j, i){
		if(G[i][j] == -1) continue;
		if(!binary_search(C.begin(), C.end(), pii(j, i)))
			tree.push_back(G[i][j]);
		else
			cycle.push_back(G[i][j]);
	}
	sort(tree.begin(), tree.end());
	sort(cycle.begin(), cycle.end());

	ll ret = (ll)INF * INF;
	if(k <= tree.size())
		ret = accumulate(tree.begin(), tree.begin()+k, 0ll);
	if(!cycle.empty()){
		ll tmp = cycle[0];
		vi me;
		reps(i, 1, cycle.size())
			me.push_back(cycle[i]);
		rep(i, tree.size())
			me.push_back(tree[i]);
		sort(me.begin(), me.end());
		tmp += accumulate(me.begin(), me.begin()+k, 0ll);
		ret = min(ret, tmp);
	}

	printf("%lld\n", ret);
	return 0;
}

/*
   9 9 6
   1 2 1
   2 3 1
   3 4 1
   4 5 1
   5 6 1
   4 7 1
   2 7 1
   7 8 1
   7 9 1
   */

Submission Info

Submission Time
Task E - 独立記念日
User natrium
Language C++ (G++ 4.6.4)
Score 100
Code Size 2442 Byte
Status AC
Exec Time 23 ms
Memory 820 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:74:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name nonloop loop
Score / Max Score 30 / 30 70 / 70
Status
AC × 34
AC × 66
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 21 ms 792 KB
loop/case_001.txt AC 19 ms 784 KB
loop/case_002.txt AC 20 ms 792 KB
loop/case_003.txt AC 20 ms 792 KB
loop/case_004.txt AC 20 ms 768 KB
loop/case_005.txt AC 20 ms 792 KB
loop/case_006.txt AC 20 ms 696 KB
loop/case_007.txt AC 20 ms 784 KB
loop/case_008.txt AC 20 ms 792 KB
loop/case_009.txt AC 20 ms 800 KB
loop/case_010.txt AC 19 ms 792 KB
loop/case_011.txt AC 20 ms 788 KB
loop/case_012.txt AC 21 ms 788 KB
loop/case_013.txt AC 19 ms 788 KB
loop/case_014.txt AC 20 ms 664 KB
loop/case_015.txt AC 21 ms 788 KB
loop/case_016.txt AC 20 ms 784 KB
loop/case_017.txt AC 20 ms 784 KB
loop/case_018.txt AC 20 ms 792 KB
loop/case_019.txt AC 20 ms 692 KB
loop/case_020.txt AC 21 ms 684 KB
loop/case_021.txt AC 19 ms 792 KB
loop/case_022.txt AC 20 ms 784 KB
loop/case_023.txt AC 22 ms 784 KB
loop/case_024.txt AC 20 ms 788 KB
loop/case_025.txt AC 21 ms 792 KB
loop/case_026.txt AC 20 ms 792 KB
loop/case_027.txt AC 20 ms 788 KB
loop/case_028.txt AC 20 ms 788 KB
loop/case_029.txt AC 19 ms 792 KB
loop/case_030.txt AC 20 ms 792 KB
loop/case_031.txt AC 20 ms 792 KB
loop/case_032.txt AC 23 ms 788 KB
loop/case_033.txt AC 23 ms 668 KB
loop/loop_case_000.txt AC 19 ms 784 KB
loop/loop_case_001.txt AC 19 ms 792 KB
loop/loop_case_002.txt AC 19 ms 784 KB
loop/loop_case_003.txt AC 20 ms 784 KB
loop/loop_case_004.txt AC 20 ms 692 KB
loop/loop_case_005.txt AC 20 ms 656 KB
loop/loop_case_006.txt AC 20 ms 688 KB
loop/loop_case_007.txt AC 20 ms 688 KB
loop/loop_case_008.txt AC 20 ms 800 KB
loop/loop_case_009.txt AC 20 ms 784 KB
loop/loop_case_010.txt AC 20 ms 692 KB
loop/loop_case_011.txt AC 19 ms 792 KB
loop/loop_case_012.txt AC 20 ms 796 KB
loop/loop_case_013.txt AC 20 ms 796 KB
loop/loop_case_014.txt AC 19 ms 796 KB
loop/loop_case_015.txt AC 20 ms 796 KB
loop/loop_case_016.txt AC 20 ms 792 KB
loop/loop_case_017.txt AC 20 ms 796 KB
loop/loop_case_018.txt AC 20 ms 800 KB
loop/loop_case_019.txt AC 19 ms 788 KB
loop/loop_case_020.txt AC 20 ms 780 KB
loop/loop_case_021.txt AC 20 ms 684 KB
loop/loop_case_022.txt AC 20 ms 696 KB
loop/loop_case_023.txt AC 20 ms 796 KB
loop/loop_case_024.txt AC 20 ms 796 KB
loop/loop_case_025.txt AC 20 ms 792 KB
loop/loop_case_026.txt AC 20 ms 792 KB
loop/loop_case_027.txt AC 21 ms 700 KB
loop/loop_case_028.txt AC 20 ms 816 KB
loop/loop_case_029.txt AC 21 ms 792 KB
loop/loop_case_030.txt AC 21 ms 788 KB
loop/loop_case_031.txt AC 20 ms 788 KB
nonloop/case_000.txt AC 20 ms 788 KB
nonloop/case_001.txt AC 20 ms 796 KB
nonloop/case_002.txt AC 20 ms 800 KB
nonloop/case_003.txt AC 20 ms 788 KB
nonloop/case_004.txt AC 20 ms 696 KB
nonloop/case_005.txt AC 20 ms 664 KB
nonloop/case_006.txt AC 19 ms 784 KB
nonloop/case_007.txt AC 20 ms 796 KB
nonloop/case_008.txt AC 20 ms 796 KB
nonloop/case_009.txt AC 20 ms 708 KB
nonloop/case_010.txt AC 20 ms 696 KB
nonloop/case_011.txt AC 20 ms 792 KB
nonloop/case_012.txt AC 20 ms 768 KB
nonloop/case_013.txt AC 21 ms 792 KB
nonloop/case_014.txt AC 20 ms 792 KB
nonloop/case_015.txt AC 20 ms 696 KB
nonloop/case_016.txt AC 20 ms 800 KB
nonloop/case_017.txt AC 20 ms 820 KB
nonloop/case_018.txt AC 20 ms 796 KB
nonloop/case_019.txt AC 19 ms 792 KB
nonloop/case_020.txt AC 21 ms 796 KB
nonloop/case_021.txt AC 20 ms 792 KB
nonloop/case_022.txt AC 20 ms 784 KB
nonloop/case_023.txt AC 22 ms 788 KB
nonloop/case_024.txt AC 19 ms 788 KB
nonloop/case_025.txt AC 20 ms 788 KB
nonloop/case_026.txt AC 20 ms 788 KB
nonloop/case_027.txt AC 20 ms 792 KB
nonloop/case_028.txt AC 19 ms 788 KB
nonloop/case_029.txt AC 20 ms 784 KB
nonloop/case_030.txt AC 20 ms 788 KB
nonloop/case_031.txt AC 21 ms 788 KB
nonloop/case_032.txt AC 22 ms 792 KB
nonloop/case_033.txt AC 22 ms 796 KB