Submission #254791

#	Time	Username	Problem	Language	Result	Execution time	Memory
254791		model_code	Graph (BOI20_graph)	C++11	100 / 100	562 ms	35316 KiB

Graph

#include <iostream>       // std::cout
#include <vector>
#include <algorithm>
#include <set>
#include <map>

/*
	BOI2020 uzdevums "Graph".
	Šķautņu garumi tiek dubultoti, lai varētu iegūt vērtības veselos skaitļos.

*/

using namespace std;

const long MAKSIS = 100001;
const int neapsk = 2;

bool ir_labi = true;
vector<long> komponente;
vector<long> ve;


class Virsotne;

Virsotne* v[MAKSIS];


class Virsotne {
	public:
	   map<long,long> uz; // šķautnes uz (virsotnes_id, šķautnes garums)
	   long koef_pie_x; // koeficients pie x: -1 vai 1, ja nav piešķirta precīza vērtība, 0 - ja ir zināma precīza vērtība, 2 - ja nav apskatīta
	   long brivais;
	   
	Virsotne() { koef_pie_x = neapsk; brivais = 0; uz.clear(); }
	   
	bool Uz(long _id, long _g) 
	{
	 if ( (uz.emplace(_id,_g)).second) return true;
      else return(uz.at(_id) == _g); 
	}
	
	void Pievieno() {
		
		for (auto mit = uz.begin(); mit != uz.end(); ++mit) 
		{
			if ( v[mit->first] -> koef_pie_x == neapsk ) 
			{ 
				v[mit->first] -> koef_pie_x = - koef_pie_x; 
				v[mit->first] -> brivais = mit->second - brivais; 
				komponente.push_back(mit->first);
			}
			else //jāpārbauda, vai var salāgot ar jau zināmu, ko esam satikuši
				if ( v[mit->first] -> koef_pie_x == - koef_pie_x ) {
					ir_labi &= ( v[mit->first] -> brivais == mit->second - brivais ); // vai ir pretruna, vai nē
				}
				else {
					// x var noteikt viennozīmīgi
					long x = (mit->second - v[mit->first] -> brivais - brivais) / (v[mit->first] -> koef_pie_x + koef_pie_x); 

					// Jāizskrien cauri visai komponentei un jāaizvieto x ar šo vērtību
					for (auto kit=komponente.begin(); kit != komponente.end(); kit++) {
						if (v[*kit] -> koef_pie_x != 0) {
							v[*kit] -> brivais += x * v[*kit] -> koef_pie_x;
							v[*kit] -> koef_pie_x = 0;
						}
						
					}
				}
		}
	return;
	}
		
};	
	
	
	void Apstrada(long virs_id) {

		// Jāizložņā dziļumā visas saistītās virsotnes un jācenšas salikt svari, ja tas ir iespējams.
		// Ja šai komponentei sanāk, ka svari nav viennozīmīgi noteikti, tad beigās jāatrod minimālā absolūto vērtību summa
		
		komponente.clear();
		
		v[virs_id] -> koef_pie_x = 1;
		v[virs_id] -> brivais = 0;
		
		komponente.push_back(virs_id);
		
		size_t ind_kompo = 0;
		
		while (ind_kompo < komponente.size()) {		
			v[komponente[ind_kompo]] -> Pievieno();
			ind_kompo++;
		}
		
		// Vai nu visām komponentē esošajām virsotnēm vērtības būs zināmas, vai arī visām nebūs!
		// Saliekam trūkstošās vērtības, ja vajag un līdz šim ir labi
		if (ir_labi && (v[*(komponente.begin())] -> koef_pie_x != 0))
		{
			// Izvelkam visas vērtības, ņemot pie -x ar pozitīvu, bet pie +x - ar negatīvu zīmi, un starp tām atrodam mediānu
			ve.clear();
			for (auto kit=komponente.begin(); kit != komponente.end(); ++kit) {
				if (v[*kit] -> koef_pie_x > 0) ve.push_back(-v[*kit] -> brivais);
				else ve.push_back(v[*kit] -> brivais);
			}
			sort(ve.begin(),ve.end());
			
			long x = ve[ve.size()/2];
			
			for (auto kit=komponente.begin(); kit != komponente.end(); kit++) 
			{
				v[*kit] -> brivais += x * v[*kit] -> koef_pie_x;
				v[*kit] -> koef_pie_x = 0;
			}
		}
		
		return;
	}	
		


  long N, M;

int main ()
{
  long _no, _uz, _gar;
  
  cin >> N; //virsotnes
  cin >> M; //šķautnes
  
  for (long i=1; i<=N; i++) v[i] = new Virsotne();
  
  while (M > 0) {
		
	cin >> _no >> _uz >> _gar;
	
	_gar *= 2;
	
	// Ielasa šķautnes un kā sliktus uzreiz atpazīst gadījumus, ja paralēli ir šķautnes ar atšķirīgiem svariem.
	if ( ((v[_no] -> Uz(_uz,_gar)) && (v[_uz] -> Uz(_no,_gar))) == false ) { ir_labi = false; goto izdruka;}
	
	M--;
  }
  
  for (long i=1; i<=N; i++) {
	  if (v[i] -> koef_pie_x == neapsk)
	  {
		 Apstrada(i);
		 if (!ir_labi) goto izdruka;
	  }
	  
  }
  
  izdruka:
  
  double d;
            if (ir_labi) {
				 cout << "YES\n";
				 for (long i=1; i<=N; i++) {
					 d = v[i] -> brivais;
					 d /= 2.0;
					 if (i>1) cout << " ";
					 cout << d;
				 }
				 cout << "\n";
			}
			else cout << "NO\n";
  
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42