oj.uz

Submission #783692

# Submission time Handle Problem Language Result Execution time Memory
783692 2023-07-15T08:33:22 Z raysh07 Graph (BOI20_graph) C++17
100 / 100
 124 ms 27984 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
const int N = 1e5 + 69;
vector <pair<int, int>> adj[N];
double ans[N];
int c[N], d[N];
bool vis[N];
int n, m;
vector <double> forced;
vector <int> comp;
 
void equate(int c1, int d1, int c2, int d2){
	if (c1 == c2){
		if (d1 == d2);
		else forced.push_back(0), forced.push_back(1);
	} else {
		assert(c1 + c2 == 0);
		//c1x + d1 = c2x + d2
		//(c1 - c2) x = d2 - d1
		// x = (d2 - d1) / (c1 - c2) 
		forced.push_back((double)(d2 - d1) / (c1 - c2));
	}
}
 
void dfs(int u){
	vis[u] = true;
	comp.push_back(u);
	for (auto [v, w] : adj[u]){
		if (vis[v]){
			equate(c[v], d[v], -c[u], w - d[u]);
		} else {
			c[v] = -c[u];
			d[v] = -d[u];
			d[v] += w;
			dfs(v);
		}
	}
}
 
void Solve()
{
	cin >> n >> m;
 
	while (m--){
		int u, v, c; cin >> u >> v >> c;
 
		adj[u].push_back({v, c});
		adj[v].push_back({u, c});
	}
 
	for (int i = 1; i <= n; i++){
		if (vis[i]) continue;
 
		comp.clear();
		forced.clear();
 
		c[i] = 1;
		d[i] = 0;
 
		dfs(i);
		
// 		cout << forced.size() << "\n";
// 		for (auto x : forced) cout << x << " ";
// 		cout << "\n";
 
		sort(forced.begin(), forced.end());
		for (int i = 1; i < forced.size(); i++){
			if (forced[i] != forced[i - 1]){
				cout << "NO\n";
				return;
			}
		}
 
		if (forced.size() == 0){
			vector <int> f;
			for (auto x : comp){
				f.push_back(d[x] * c[x]);
			}
 
			sort(f.begin(), f.end());
			forced.push_back(-f[(int)f.size() / 2]);
		}
 
		double val = forced[0];
		
		for (auto x : comp){
			ans[x] = val * c[x] + d[x];
		}
	}
	cout << "YES\n";
	cout << fixed << setprecision(10);
	for (int i = 1; i <= n; i++){
		cout << ans[i] << " \n"[i == n];
	}
}
 
int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
 
   // freopen("in",  "r", stdin);
   // freopen("out", "w", stdout);
 
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message

Graph.cpp: In function 'void Solve()':
Graph.cpp:74:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int i = 1; i < forced.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2684 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2684 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 1 ms 2684 KB answer = NO
10 Correct 1 ms 2644 KB answer = YES
11 Correct 2 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2680 KB answer = YES
16 Correct 1 ms 2644 KB answer = YES
17 Correct 2 ms 2676 KB answer = YES
18 Correct 1 ms 2644 KB answer = YES
19 Correct 2 ms 2680 KB answer = YES
20 Correct 2 ms 2684 KB answer = YES
21 Correct 1 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2684 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2684 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 1 ms 2684 KB answer = NO
10 Correct 1 ms 2644 KB answer = YES
11 Correct 2 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2680 KB answer = YES
16 Correct 1 ms 2644 KB answer = YES
17 Correct 2 ms 2676 KB answer = YES
18 Correct 1 ms 2644 KB answer = YES
19 Correct 2 ms 2680 KB answer = YES
20 Correct 2 ms 2684 KB answer = YES
21 Correct 1 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 1 ms 2644 KB answer = YES
25 Correct 1 ms 2684 KB answer = YES
26 Correct 1 ms 2644 KB answer = YES
27 Correct 1 ms 2628 KB answer = YES
28 Correct 1 ms 2644 KB answer = YES
29 Correct 1 ms 2644 KB answer = YES
30 Correct 1 ms 2680 KB answer = NO
31 Correct 1 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 1 ms 2676 KB answer = YES
34 Correct 1 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 1 ms 2644 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2684 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2684 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 1 ms 2684 KB answer = NO
10 Correct 1 ms 2644 KB answer = YES
11 Correct 2 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2680 KB answer = YES
16 Correct 1 ms 2644 KB answer = YES
17 Correct 2 ms 2676 KB answer = YES
18 Correct 1 ms 2644 KB answer = YES
19 Correct 2 ms 2680 KB answer = YES
20 Correct 2 ms 2684 KB answer = YES
21 Correct 1 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 1 ms 2644 KB answer = YES
25 Correct 1 ms 2684 KB answer = YES
26 Correct 1 ms 2644 KB answer = YES
27 Correct 1 ms 2628 KB answer = YES
28 Correct 1 ms 2644 KB answer = YES
29 Correct 1 ms 2644 KB answer = YES
30 Correct 1 ms 2680 KB answer = NO
31 Correct 1 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 1 ms 2676 KB answer = YES
34 Correct 1 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 1 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2676 KB answer = YES
39 Correct 2 ms 2772 KB answer = YES
40 Correct 2 ms 2772 KB answer = YES
41 Correct 2 ms 2772 KB answer = NO
42 Correct 2 ms 2824 KB answer = YES
43 Correct 3 ms 2772 KB answer = YES
44 Correct 2 ms 2772 KB answer = YES
45 Correct 2 ms 2772 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2812 KB answer = YES
48 Correct 2 ms 2772 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2684 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2684 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 1 ms 2684 KB answer = NO
10 Correct 1 ms 2644 KB answer = YES
11 Correct 2 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2680 KB answer = YES
16 Correct 1 ms 2644 KB answer = YES
17 Correct 2 ms 2676 KB answer = YES
18 Correct 1 ms 2644 KB answer = YES
19 Correct 2 ms 2680 KB answer = YES
20 Correct 2 ms 2684 KB answer = YES
21 Correct 1 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 1 ms 2644 KB answer = YES
25 Correct 1 ms 2684 KB answer = YES
26 Correct 1 ms 2644 KB answer = YES
27 Correct 1 ms 2628 KB answer = YES
28 Correct 1 ms 2644 KB answer = YES
29 Correct 1 ms 2644 KB answer = YES
30 Correct 1 ms 2680 KB answer = NO
31 Correct 1 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 1 ms 2676 KB answer = YES
34 Correct 1 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 1 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2676 KB answer = YES
39 Correct 2 ms 2772 KB answer = YES
40 Correct 2 ms 2772 KB answer = YES
41 Correct 2 ms 2772 KB answer = NO
42 Correct 2 ms 2824 KB answer = YES
43 Correct 3 ms 2772 KB answer = YES
44 Correct 2 ms 2772 KB answer = YES
45 Correct 2 ms 2772 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2812 KB answer = YES
48 Correct 2 ms 2772 KB answer = YES
49 Correct 8 ms 3844 KB answer = YES
50 Correct 8 ms 4180 KB answer = YES
51 Correct 8 ms 4148 KB answer = YES
52 Correct 5 ms 3924 KB answer = NO
53 Correct 2 ms 2772 KB answer = YES
54 Correct 3 ms 2900 KB answer = YES
55 Correct 5 ms 3284 KB answer = YES
56 Correct 8 ms 3844 KB answer = YES
57 Correct 8 ms 3668 KB answer = YES
58 Correct 7 ms 3668 KB answer = YES
59 Correct 8 ms 3668 KB answer = YES
60 Correct 8 ms 3796 KB answer = YES
61 Correct 5 ms 3284 KB answer = YES
62 Correct 68 ms 23092 KB answer = NO
63 Correct 52 ms 16968 KB answer = YES
64 Correct 49 ms 16968 KB answer = NO
65 Correct 53 ms 16904 KB answer = YES
66 Correct 3 ms 2900 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2684 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2684 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 1 ms 2684 KB answer = NO
10 Correct 1 ms 2644 KB answer = YES
11 Correct 2 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2680 KB answer = YES
16 Correct 1 ms 2644 KB answer = YES
17 Correct 2 ms 2676 KB answer = YES
18 Correct 1 ms 2644 KB answer = YES
19 Correct 2 ms 2680 KB answer = YES
20 Correct 2 ms 2684 KB answer = YES
21 Correct 1 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 1 ms 2644 KB answer = YES
25 Correct 1 ms 2684 KB answer = YES
26 Correct 1 ms 2644 KB answer = YES
27 Correct 1 ms 2628 KB answer = YES
28 Correct 1 ms 2644 KB answer = YES
29 Correct 1 ms 2644 KB answer = YES
30 Correct 1 ms 2680 KB answer = NO
31 Correct 1 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 1 ms 2676 KB answer = YES
34 Correct 1 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 1 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2676 KB answer = YES
39 Correct 2 ms 2772 KB answer = YES
40 Correct 2 ms 2772 KB answer = YES
41 Correct 2 ms 2772 KB answer = NO
42 Correct 2 ms 2824 KB answer = YES
43 Correct 3 ms 2772 KB answer = YES
44 Correct 2 ms 2772 KB answer = YES
45 Correct 2 ms 2772 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2812 KB answer = YES
48 Correct 2 ms 2772 KB answer = YES
49 Correct 8 ms 3844 KB answer = YES
50 Correct 8 ms 4180 KB answer = YES
51 Correct 8 ms 4148 KB answer = YES
52 Correct 5 ms 3924 KB answer = NO
53 Correct 2 ms 2772 KB answer = YES
54 Correct 3 ms 2900 KB answer = YES
55 Correct 5 ms 3284 KB answer = YES
56 Correct 8 ms 3844 KB answer = YES
57 Correct 8 ms 3668 KB answer = YES
58 Correct 7 ms 3668 KB answer = YES
59 Correct 8 ms 3668 KB answer = YES
60 Correct 8 ms 3796 KB answer = YES
61 Correct 5 ms 3284 KB answer = YES
62 Correct 68 ms 23092 KB answer = NO
63 Correct 52 ms 16968 KB answer = YES
64 Correct 49 ms 16968 KB answer = NO
65 Correct 53 ms 16904 KB answer = YES
66 Correct 3 ms 2900 KB answer = YES
67 Correct 77 ms 19732 KB answer = YES
68 Correct 64 ms 19572 KB answer = YES
69 Correct 64 ms 19556 KB answer = YES
70 Correct 96 ms 27984 KB answer = YES
71 Correct 71 ms 19628 KB answer = YES
72 Correct 76 ms 13888 KB answer = YES
73 Correct 70 ms 13760 KB answer = YES
74 Correct 52 ms 13000 KB answer = YES
75 Correct 21 ms 11468 KB answer = NO
76 Correct 9 ms 4060 KB answer = YES
77 Correct 18 ms 5480 KB answer = YES
78 Correct 40 ms 7640 KB answer = YES
79 Correct 60 ms 12172 KB answer = YES
80 Correct 57 ms 12952 KB answer = YES
81 Correct 31 ms 14464 KB answer = NO
82 Correct 80 ms 19212 KB answer = YES
83 Correct 91 ms 20304 KB answer = YES
84 Correct 95 ms 20336 KB answer = YES
85 Correct 75 ms 19752 KB answer = YES
86 Correct 78 ms 19764 KB answer = YES
87 Correct 36 ms 13788 KB answer = NO
88 Correct 86 ms 16196 KB answer = YES
89 Correct 68 ms 12364 KB answer = YES
90 Correct 67 ms 12444 KB answer = YES
91 Correct 75 ms 12984 KB answer = YES
92 Correct 35 ms 8240 KB answer = YES
93 Correct 33 ms 8256 KB answer = YES
94 Correct 46 ms 18104 KB answer = NO
95 Correct 31 ms 11664 KB answer = NO
96 Correct 124 ms 24924 KB answer = YES
97 Correct 29 ms 17528 KB answer = NO