# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
254791 |
2020-07-30T15:26:18 Z |
model_code |
Graph (BOI20_graph) |
C++11 |
|
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 |