Submission #254791

# Submission time Handle Problem Language Result Execution time Memory
254791 2020-07-30T15:26:18 Z model_code Graph (BOI20_graph) C++11
100 / 100
562 ms 35316 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB answer = YES
2 Correct 0 ms 256 KB answer = YES
3 Correct 0 ms 256 KB answer = YES
4 Correct 0 ms 256 KB answer = NO
5 Correct 0 ms 256 KB answer = YES
6 Correct 1 ms 256 KB answer = YES
7 Correct 1 ms 256 KB answer = YES
8 Correct 0 ms 256 KB answer = YES
9 Correct 0 ms 256 KB answer = NO
10 Correct 1 ms 256 KB answer = YES
11 Correct 0 ms 256 KB answer = YES
12 Correct 0 ms 256 KB answer = NO
13 Correct 1 ms 256 KB answer = YES
14 Correct 1 ms 256 KB answer = YES
15 Correct 0 ms 256 KB answer = YES
16 Correct 1 ms 256 KB answer = YES
17 Correct 0 ms 256 KB answer = YES
18 Correct 1 ms 256 KB answer = YES
19 Correct 1 ms 256 KB answer = YES
20 Correct 1 ms 256 KB answer = YES
21 Correct 0 ms 256 KB answer = YES
22 Correct 0 ms 256 KB answer = NO
23 Correct 0 ms 256 KB answer = NO
# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB answer = YES
2 Correct 0 ms 256 KB answer = YES
3 Correct 0 ms 256 KB answer = YES
4 Correct 0 ms 256 KB answer = NO
5 Correct 0 ms 256 KB answer = YES
6 Correct 1 ms 256 KB answer = YES
7 Correct 1 ms 256 KB answer = YES
8 Correct 0 ms 256 KB answer = YES
9 Correct 0 ms 256 KB answer = NO
10 Correct 1 ms 256 KB answer = YES
11 Correct 0 ms 256 KB answer = YES
12 Correct 0 ms 256 KB answer = NO
13 Correct 1 ms 256 KB answer = YES
14 Correct 1 ms 256 KB answer = YES
15 Correct 0 ms 256 KB answer = YES
16 Correct 1 ms 256 KB answer = YES
17 Correct 0 ms 256 KB answer = YES
18 Correct 1 ms 256 KB answer = YES
19 Correct 1 ms 256 KB answer = YES
20 Correct 1 ms 256 KB answer = YES
21 Correct 0 ms 256 KB answer = YES
22 Correct 0 ms 256 KB answer = NO
23 Correct 0 ms 256 KB answer = NO
24 Correct 0 ms 384 KB answer = YES
25 Correct 0 ms 384 KB answer = YES
26 Correct 0 ms 384 KB answer = YES
27 Correct 1 ms 384 KB answer = YES
28 Correct 1 ms 384 KB answer = YES
29 Correct 0 ms 384 KB answer = YES
30 Correct 0 ms 384 KB answer = NO
31 Correct 1 ms 384 KB answer = YES
32 Correct 1 ms 384 KB answer = YES
33 Correct 1 ms 384 KB answer = YES
34 Correct 1 ms 384 KB answer = YES
35 Correct 1 ms 384 KB answer = YES
36 Correct 0 ms 384 KB answer = YES
# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB answer = YES
2 Correct 0 ms 256 KB answer = YES
3 Correct 0 ms 256 KB answer = YES
4 Correct 0 ms 256 KB answer = NO
5 Correct 0 ms 256 KB answer = YES
6 Correct 1 ms 256 KB answer = YES
7 Correct 1 ms 256 KB answer = YES
8 Correct 0 ms 256 KB answer = YES
9 Correct 0 ms 256 KB answer = NO
10 Correct 1 ms 256 KB answer = YES
11 Correct 0 ms 256 KB answer = YES
12 Correct 0 ms 256 KB answer = NO
13 Correct 1 ms 256 KB answer = YES
14 Correct 1 ms 256 KB answer = YES
15 Correct 0 ms 256 KB answer = YES
16 Correct 1 ms 256 KB answer = YES
17 Correct 0 ms 256 KB answer = YES
18 Correct 1 ms 256 KB answer = YES
19 Correct 1 ms 256 KB answer = YES
20 Correct 1 ms 256 KB answer = YES
21 Correct 0 ms 256 KB answer = YES
22 Correct 0 ms 256 KB answer = NO
23 Correct 0 ms 256 KB answer = NO
24 Correct 0 ms 384 KB answer = YES
25 Correct 0 ms 384 KB answer = YES
26 Correct 0 ms 384 KB answer = YES
27 Correct 1 ms 384 KB answer = YES
28 Correct 1 ms 384 KB answer = YES
29 Correct 0 ms 384 KB answer = YES
30 Correct 0 ms 384 KB answer = NO
31 Correct 1 ms 384 KB answer = YES
32 Correct 1 ms 384 KB answer = YES
33 Correct 1 ms 384 KB answer = YES
34 Correct 1 ms 384 KB answer = YES
35 Correct 1 ms 384 KB answer = YES
36 Correct 0 ms 384 KB answer = YES
37 Correct 1 ms 384 KB answer = YES
38 Correct 1 ms 384 KB answer = YES
39 Correct 2 ms 384 KB answer = YES
40 Correct 3 ms 512 KB answer = YES
41 Correct 1 ms 512 KB answer = NO
42 Correct 2 ms 512 KB answer = YES
43 Correct 3 ms 512 KB answer = YES
44 Correct 2 ms 512 KB answer = YES
45 Correct 3 ms 512 KB answer = YES
46 Correct 1 ms 384 KB answer = YES
47 Correct 2 ms 512 KB answer = YES
48 Correct 2 ms 512 KB answer = YES
# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB answer = YES
2 Correct 0 ms 256 KB answer = YES
3 Correct 0 ms 256 KB answer = YES
4 Correct 0 ms 256 KB answer = NO
5 Correct 0 ms 256 KB answer = YES
6 Correct 1 ms 256 KB answer = YES
7 Correct 1 ms 256 KB answer = YES
8 Correct 0 ms 256 KB answer = YES
9 Correct 0 ms 256 KB answer = NO
10 Correct 1 ms 256 KB answer = YES
11 Correct 0 ms 256 KB answer = YES
12 Correct 0 ms 256 KB answer = NO
13 Correct 1 ms 256 KB answer = YES
14 Correct 1 ms 256 KB answer = YES
15 Correct 0 ms 256 KB answer = YES
16 Correct 1 ms 256 KB answer = YES
17 Correct 0 ms 256 KB answer = YES
18 Correct 1 ms 256 KB answer = YES
19 Correct 1 ms 256 KB answer = YES
20 Correct 1 ms 256 KB answer = YES
21 Correct 0 ms 256 KB answer = YES
22 Correct 0 ms 256 KB answer = NO
23 Correct 0 ms 256 KB answer = NO
24 Correct 0 ms 384 KB answer = YES
25 Correct 0 ms 384 KB answer = YES
26 Correct 0 ms 384 KB answer = YES
27 Correct 1 ms 384 KB answer = YES
28 Correct 1 ms 384 KB answer = YES
29 Correct 0 ms 384 KB answer = YES
30 Correct 0 ms 384 KB answer = NO
31 Correct 1 ms 384 KB answer = YES
32 Correct 1 ms 384 KB answer = YES
33 Correct 1 ms 384 KB answer = YES
34 Correct 1 ms 384 KB answer = YES
35 Correct 1 ms 384 KB answer = YES
36 Correct 0 ms 384 KB answer = YES
37 Correct 1 ms 384 KB answer = YES
38 Correct 1 ms 384 KB answer = YES
39 Correct 2 ms 384 KB answer = YES
40 Correct 3 ms 512 KB answer = YES
41 Correct 1 ms 512 KB answer = NO
42 Correct 2 ms 512 KB answer = YES
43 Correct 3 ms 512 KB answer = YES
44 Correct 2 ms 512 KB answer = YES
45 Correct 3 ms 512 KB answer = YES
46 Correct 1 ms 384 KB answer = YES
47 Correct 2 ms 512 KB answer = YES
48 Correct 2 ms 512 KB answer = YES
49 Correct 17 ms 2688 KB answer = YES
50 Correct 18 ms 2688 KB answer = YES
51 Correct 25 ms 2792 KB answer = YES
52 Correct 14 ms 2688 KB answer = NO
53 Correct 2 ms 512 KB answer = YES
54 Correct 5 ms 896 KB answer = YES
55 Correct 9 ms 1536 KB answer = YES
56 Correct 18 ms 2688 KB answer = YES
57 Correct 17 ms 2432 KB answer = YES
58 Correct 19 ms 2432 KB answer = YES
59 Correct 16 ms 2304 KB answer = YES
60 Correct 17 ms 2560 KB answer = YES
61 Correct 9 ms 1536 KB answer = YES
62 Correct 15 ms 2560 KB answer = NO
63 Correct 487 ms 26144 KB answer = YES
64 Correct 488 ms 26008 KB answer = NO
65 Correct 562 ms 26104 KB answer = YES
66 Correct 6 ms 824 KB answer = YES
# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB answer = YES
2 Correct 0 ms 256 KB answer = YES
3 Correct 0 ms 256 KB answer = YES
4 Correct 0 ms 256 KB answer = NO
5 Correct 0 ms 256 KB answer = YES
6 Correct 1 ms 256 KB answer = YES
7 Correct 1 ms 256 KB answer = YES
8 Correct 0 ms 256 KB answer = YES
9 Correct 0 ms 256 KB answer = NO
10 Correct 1 ms 256 KB answer = YES
11 Correct 0 ms 256 KB answer = YES
12 Correct 0 ms 256 KB answer = NO
13 Correct 1 ms 256 KB answer = YES
14 Correct 1 ms 256 KB answer = YES
15 Correct 0 ms 256 KB answer = YES
16 Correct 1 ms 256 KB answer = YES
17 Correct 0 ms 256 KB answer = YES
18 Correct 1 ms 256 KB answer = YES
19 Correct 1 ms 256 KB answer = YES
20 Correct 1 ms 256 KB answer = YES
21 Correct 0 ms 256 KB answer = YES
22 Correct 0 ms 256 KB answer = NO
23 Correct 0 ms 256 KB answer = NO
24 Correct 0 ms 384 KB answer = YES
25 Correct 0 ms 384 KB answer = YES
26 Correct 0 ms 384 KB answer = YES
27 Correct 1 ms 384 KB answer = YES
28 Correct 1 ms 384 KB answer = YES
29 Correct 0 ms 384 KB answer = YES
30 Correct 0 ms 384 KB answer = NO
31 Correct 1 ms 384 KB answer = YES
32 Correct 1 ms 384 KB answer = YES
33 Correct 1 ms 384 KB answer = YES
34 Correct 1 ms 384 KB answer = YES
35 Correct 1 ms 384 KB answer = YES
36 Correct 0 ms 384 KB answer = YES
37 Correct 1 ms 384 KB answer = YES
38 Correct 1 ms 384 KB answer = YES
39 Correct 2 ms 384 KB answer = YES
40 Correct 3 ms 512 KB answer = YES
41 Correct 1 ms 512 KB answer = NO
42 Correct 2 ms 512 KB answer = YES
43 Correct 3 ms 512 KB answer = YES
44 Correct 2 ms 512 KB answer = YES
45 Correct 3 ms 512 KB answer = YES
46 Correct 1 ms 384 KB answer = YES
47 Correct 2 ms 512 KB answer = YES
48 Correct 2 ms 512 KB answer = YES
49 Correct 17 ms 2688 KB answer = YES
50 Correct 18 ms 2688 KB answer = YES
51 Correct 25 ms 2792 KB answer = YES
52 Correct 14 ms 2688 KB answer = NO
53 Correct 2 ms 512 KB answer = YES
54 Correct 5 ms 896 KB answer = YES
55 Correct 9 ms 1536 KB answer = YES
56 Correct 18 ms 2688 KB answer = YES
57 Correct 17 ms 2432 KB answer = YES
58 Correct 19 ms 2432 KB answer = YES
59 Correct 16 ms 2304 KB answer = YES
60 Correct 17 ms 2560 KB answer = YES
61 Correct 9 ms 1536 KB answer = YES
62 Correct 15 ms 2560 KB answer = NO
63 Correct 487 ms 26144 KB answer = YES
64 Correct 488 ms 26008 KB answer = NO
65 Correct 562 ms 26104 KB answer = YES
66 Correct 6 ms 824 KB answer = YES
67 Correct 193 ms 23792 KB answer = YES
68 Correct 175 ms 23768 KB answer = YES
69 Correct 182 ms 22644 KB answer = YES
70 Correct 295 ms 35188 KB answer = YES
71 Correct 171 ms 22816 KB answer = YES
72 Correct 264 ms 23792 KB answer = YES
73 Correct 256 ms 22644 KB answer = YES
74 Correct 124 ms 14964 KB answer = YES
75 Correct 96 ms 14840 KB answer = NO
76 Correct 21 ms 3192 KB answer = YES
77 Correct 48 ms 6136 KB answer = YES
78 Correct 101 ms 10476 KB answer = YES
79 Correct 209 ms 20460 KB answer = YES
80 Correct 136 ms 15484 KB answer = YES
81 Correct 151 ms 22644 KB answer = NO
82 Correct 222 ms 22896 KB answer = YES
83 Correct 243 ms 22764 KB answer = YES
84 Correct 235 ms 23796 KB answer = YES
85 Correct 195 ms 23792 KB answer = YES
86 Correct 179 ms 22736 KB answer = YES
87 Correct 183 ms 21880 KB answer = NO
88 Correct 252 ms 22376 KB answer = YES
89 Correct 213 ms 21752 KB answer = YES
90 Correct 214 ms 21752 KB answer = YES
91 Correct 227 ms 21752 KB answer = YES
92 Correct 123 ms 11632 KB answer = YES
93 Correct 133 ms 11684 KB answer = YES
94 Correct 220 ms 22640 KB answer = NO
95 Correct 173 ms 21368 KB answer = NO
96 Correct 516 ms 35316 KB answer = YES
97 Correct 126 ms 22644 KB answer = NO