# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
722728 |
2023-04-12T18:23:34 Z |
gagik_2007 |
Graph (BOI20_graph) |
C++17 |
|
3 ms |
5032 KB |
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 31;
ll n, m, k;
vector<pair<int, int>>g[N];
bool used[N];
bool neg[N]; // if the x in the value formula has the negative sign
ll val[N]; // if neg[v]: value = val[v] - x, else: value = x + val[v]
bool defined_value = false;
ll vlx2 = 0;
void dfs(int v, int par) {
for (auto e : g[v]) {
int to = e.ff;
int c = e.ss;
if (to != par) {
if (!used[to]) {
if (neg[v]) {
val[to] = c - val[v];
}
else {
neg[to] = true;
val[to] = c - val[v];
}
used[to] = true;
dfs(to, v);
}
else {
if (neg[v] == neg[to]) {
if (neg[v]) {
if (!defined_value) {
vlx2 = val[v] + val[to] - c;
defined_value = true;
}
else if (vlx2 != val[v] + val[to] - c) {
cout << "NO\n";
exit(0);
}
}
else {
if (!defined_value) {
vlx2 = c - val[v] - val[to];
defined_value = true;
}
else if (vlx2 != c - val[v] - val[to]) {
cout << "NO\n";
exit(0);
}
}
}
else {
if (val[v] + val[to] != c) {
cout << "NO\n";
exit(0);
}
}
}
}
}
}
ll get_sum(ll curvlx2) {
//cout << "PROCESSING: " << curvlx2 << endl;
ll sum = 0;
for (int v = 1; v <= n; v++) {
ll vl = 0;
if (neg[v]) {
vl = val[v] * 2 - curvlx2;
}
else {
vl = val[v] * 2 + curvlx2;
}
//cout << vl << " ";
sum += abs(vl);
}
//cout << endl;
return sum;
}
int main() {
//freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
int tp;
cin >> x >> y >> tp;
g[x].push_back({ y,tp });
g[y].push_back({ x,tp });
}
for (int v = 1; v <= n; v++) {
if (!used[v]) {
dfs(v, -1);
}
}
cout << setprecision(12) << fixed;
cout << "YES\n";
if (defined_value) {
for (int v = 1; v <= n; v++) {
ld vl = 0;
if (neg[v]) {
vl = val[v] - ld(vlx2) / 2.0;
}
else {
vl = val[v] + ld(vlx2) / 2.0;
}
cout << vl << " ";
}
cout << endl;
}
else {
pair<ll, ll>mn = { INF,INF };
for (int v = 1; v <= n; v++) {
ll cur = 0;
if (neg[v]) {
cur = val[v];
}
else {
cur = -val[v];
}
//cout << cur << " " << get_sum(cur) << endl;
mn = min(mn, { get_sum(cur),cur });
}
vlx2 = mn.ss;
for (int v = 1; v <= n; v++) {
ld vl = 0;
if (neg[v]) {
vl = val[v] - ld(vlx2) / 2.0;
}
else {
vl = val[v] + ld(vlx2) / 2.0;
}
cout << vl << " ";
}
cout << endl;
}
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
2 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
3 ms |
4948 KB |
answer = YES |
9 |
Correct |
3 ms |
4948 KB |
answer = NO |
10 |
Correct |
3 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
3 ms |
4944 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
3 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Incorrect |
3 ms |
5032 KB |
jury has the better answer: jans = YES, pans = NO |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
2 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
3 ms |
4948 KB |
answer = YES |
9 |
Correct |
3 ms |
4948 KB |
answer = NO |
10 |
Correct |
3 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
3 ms |
4944 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
3 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Incorrect |
3 ms |
5032 KB |
jury has the better answer: jans = YES, pans = NO |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
2 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
3 ms |
4948 KB |
answer = YES |
9 |
Correct |
3 ms |
4948 KB |
answer = NO |
10 |
Correct |
3 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
3 ms |
4944 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
3 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Incorrect |
3 ms |
5032 KB |
jury has the better answer: jans = YES, pans = NO |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
2 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
3 ms |
4948 KB |
answer = YES |
9 |
Correct |
3 ms |
4948 KB |
answer = NO |
10 |
Correct |
3 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
3 ms |
4944 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
3 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Incorrect |
3 ms |
5032 KB |
jury has the better answer: jans = YES, pans = NO |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
2 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
3 ms |
4948 KB |
answer = YES |
9 |
Correct |
3 ms |
4948 KB |
answer = NO |
10 |
Correct |
3 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
3 ms |
4944 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
3 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Incorrect |
3 ms |
5032 KB |
jury has the better answer: jans = YES, pans = NO |
20 |
Halted |
0 ms |
0 KB |
- |