Submission #433827

#	Time	Username	Problem	Language	Result	Execution time	Memory
433827		JeanBombeur	Bridges (APIO19_bridges)	C++17	14 / 100	107 ms	3660 KiB

bridges

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

//   <|°_°|>

const int MAX_NOEUDS = (100 * 1000);

struct arete {
	int dep, fin, poids;
};

arete Aretes[2 * MAX_NOEUDS];

arete Requetes[MAX_NOEUDS];
int Ans[MAX_NOEUDS];

int Dsu[MAX_NOEUDS];

int nbNoeuds, nbAretes, nbRequetes;

bool operator<(arete a, arete b) {
	return a.poids > b.poids;
}

int Find(int a) {
	if (Dsu[a] < 0)
		return a;
	return Dsu[a] = Find(Dsu[a]);
}

void Union(int id) {
	int ra = Find(Aretes[id].dep), rb = Find(Aretes[id].fin);
	if (ra == rb)
		return;
	if (Dsu[ra] > Dsu[rb])
		swap(ra, rb);
	Dsu[ra] += Dsu[rb];
	Dsu[rb] = ra;
	return;
}

void Read() {
	scanf("%d %d", &nbNoeuds, &nbAretes);
	fill_n(Dsu, nbNoeuds, -1);
	for (int i = 0; i < nbAretes; i ++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		Aretes[i] = {-- a, -- b, c};
	}
	sort(Aretes, Aretes + nbAretes);
	return;
}

void Solve() {
	scanf("%d", &nbRequetes);
	for (int i = 0; i < nbRequetes; i ++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		Requetes[i] = {-- b, i, c};
	}
	sort(Requetes, Requetes + nbRequetes);
	int curArete = 0;
	for (int i = 0; i < nbRequetes; i ++)
	{
		while (curArete < nbAretes && Aretes[curArete].poids >= Requetes[i].poids)
			Union(curArete ++);
		Ans[Requetes[i].fin] = - Dsu[Find(Requetes[i].dep)];
	}
	for (int i = 0; i < nbRequetes; i ++)
	{
		printf("%d\n", Ans[i]);
	}
	return;
}

int main() {
	Read();
	Solve();
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void Read()':
bridges.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d %d", &nbNoeuds, &nbAretes);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void Solve()':
bridges.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d", &nbRequetes);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27