Submission #1013584

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1013584	2024-07-03T16:45:04 Z	vjudge1	timeismoney (balkan11_timeismoney)	C++17	40 / 100	12 ms	2320 KB

timeismoney

#include <bits/stdc++.h>
using namespace std;

typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll;
#define MEMSET_MAX 0x7f
#define testcases \
  int test_amount;        \
  cin >> test_amount;       \
  while (test_amount--)
const ll inf = 1e16; const int mod = 1e9+7;

ll n, m, sum, x, y, t, c, tsum, csum;
bool visited[203];
vector<pair<ll, pll>> adj[203];
set<pair<ll, pll>> e; 
pair<ll, pll> w;
vector<pll> res;
map<pll, bool> mp;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  cin >> n >> m;
  
  for (int i = 1; i <= m; i++) {
  	cin >> x >> y >> t >> c;
  	adj[x].push_back({t, {x, y}});
  	adj[y].push_back({t, {x, y}});
  	tsum += t; csum += c;
  	res.push_back({x, y});
  }
  
  if (m == n-1) {
  	cout << tsum << " " << csum << "\n";
  	for (auto i : res) cout << i.first << " " << i.second << "\n";
  	return 0;
  }
  
  res.clear();
  
  visited[0] = 1;
  for (auto i : adj[0]) {e.insert(i); mp[{i.second.first, i.second.second}] = 1;}
  
  while (!e.empty()) {	
	w = (*e.begin());
  	
  	if (visited[(*e.begin()).second.first] == 0 || visited[(*e.begin()).second.second] == 0) {
  		sum += (*e.begin()).first;
  		
  		x = (*e.begin()).second.first; y = (*e.begin()).second.second;
  		//cout << "edge " << x << " " << y << "\n";
  		
  		if (!visited[x]) for (auto i : adj[x]) {
  			//cout << i.second.first << " " << i.second.second << " " << mp[{i.second.first, i.second.second}] << "\n";
  			 	
  			if (mp[{i.second.first, i.second.second}]) continue;
  			e.insert(i); mp[{i.second.first, i.second.second}] = 1;
		}
		
  		if (!visited[y]) for (auto i : adj[y]) {
  			//cout << i.second.first << " " << i.second.second << " " << mp[{i.second.first, i.second.second}] << "\n";
  			
  			if (mp[{i.second.first, i.second.second}]) continue;
  			e.insert(i); mp[{i.second.first, i.second.second}] = 1;
		}
  		
		visited[x] = 1; visited[y] = 1;
		res.push_back({x, y});
	}
  	e.erase(w);
  }
  
  for (auto i : e) {
  	if (visited[i.second.first] == 0 || visited[i.second.second] == 0) {
	  	sum += i.first;
	  	visited[i.second.first] = 1; visited[i.second.second] = 1;
	  	res.push_back({i.second.first, i.second.second});
	}
  }
  
  cout << sum << " " << sum << "\n";
  for (auto i : res) cout << i.first << " " << i.second << "\n";   

  return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	2 ms	860 KB	Output is correct
8	Correct	9 ms	2320 KB	Output is correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Incorrect	1 ms	348 KB	Output isn't correct
11	Incorrect	0 ms	348 KB	Output isn't correct
12	Incorrect	0 ms	348 KB	Output isn't correct
13	Incorrect	0 ms	348 KB	Output isn't correct
14	Incorrect	1 ms	348 KB	Output isn't correct
15	Incorrect	1 ms	348 KB	Output isn't correct
16	Incorrect	2 ms	860 KB	Output isn't correct
17	Incorrect	2 ms	860 KB	Output isn't correct
18	Incorrect	2 ms	860 KB	Output isn't correct
19	Incorrect	12 ms	2264 KB	Output isn't correct
20	Incorrect	9 ms	2264 KB	Output isn't correct