Submission #433635

#	Time	Username	Problem	Language	Result	Execution time	Memory
433635		Mounir	Bridges (APIO19_bridges)	C++14	13 / 100	3097 ms	14712 KiB

bridges

#include <bits/stdc++.h>
#define chmax(x, v) x = max(x, v)
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define int long long
using namespace std;

const int N = 1e5;
vector<pii> aretes[N];
int numNoeud[N], numVoisin[N];
int noeudArete[N], voisinArete[N];
bool vu[N];

int dfs(int noeud, int poids){
	vu[noeud] = true;
	int nb = 1;

	for (pii arete : aretes[noeud]){
		if (poids <= arete.second && !vu[arete.first])
			nb += dfs(arete.first, poids);
	}
	return nb;
}

signed main(){
	int nNoeuds, nAretes; cin >> nNoeuds >> nAretes;
	for (int iArete = 0; iArete < nAretes; ++iArete){
		int noeud, voisin, poids; cin >> noeud >> voisin >> poids;
		--noeud, --voisin;
		noeudArete[iArete] = noeud;
		voisinArete[iArete] = voisin;
		
		numNoeud[iArete] = sz(aretes[noeud]);
		numVoisin[iArete] = sz(aretes[voisin]);
		aretes[noeud].pb({voisin, poids});
		aretes[voisin].pb({noeud, poids});
	}

	int nReqs; cin >> nReqs;
	for (int iReq = 0; iReq < nReqs; ++iReq){
		int typeReq; cin >> typeReq;
		if (typeReq == 1){
			int iArete, poids; cin >> iArete >> poids; --iArete;
			aretes[noeudArete[iArete]][numNoeud[iArete]].second = poids;
			aretes[voisinArete[iArete]][numVoisin[iArete]].second = poids;
		}
		else {
			for (int noeud = 0; noeud < nNoeuds; ++noeud)
				vu[noeud] = false;
			int poids, depart; cin >> depart >> poids; --depart;
			cout << dfs(depart, poids) << endl;
		}
	}
	return 0;
}

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