oj.uz

Submission #1012537

# Submission time Handle Problem Language Result Execution time Memory
1012537 2024-07-02T09:54:33 Z vjudge1 timeismoney (balkan11_timeismoney) C++17
40 / 100
 9 ms 2388 KB 
#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;
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}});
  }
  
  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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 9 ms 2388 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 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 0 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 8 ms 2352 KB Output isn't correct
20 Incorrect 7 ms 2140 KB Output isn't correct