답안 #254791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254791	2020-07-30T15:26:18 Z	model_code	Graph (BOI20_graph)	C++11	100 / 100	562 ms	35316 KB

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.0 / 5.0

#	결과	실행 시간	메모리	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

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	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

Subtask #3
17.0 / 17.0

#	결과	실행 시간	메모리	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

Subtask #4
24.0 / 24.0

#	결과	실행 시간	메모리	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

Subtask #5
42.0 / 42.0

#	결과	실행 시간	메모리	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

답안 #254791

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 12.0 / 12.0

Subtask #3 17.0 / 17.0

Subtask #4 24.0 / 24.0

Subtask #5 42.0 / 42.0

Subtask #1
5.0 / 5.0

Subtask #2
12.0 / 12.0

Subtask #3
17.0 / 17.0

Subtask #4
24.0 / 24.0

Subtask #5
42.0 / 42.0