oj.uz

Submission #973946

# Submission time Handle Problem Language Result Execution time Memory
973946 2024-05-02T13:17:56 Z NotLinux Graph (BOI20_graph) C++17
100 / 100
 151 ms 29128 KB 
//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
#define int long long
#define double long double
const int N = 1e5 + 7;
const int inf = 1e9 + 7;
const double EPS = 0.00000001;
const double INF = 1e9 + 7;
int n,m;
vector < pair < int , int > > graph[N];
pair < int , int > mem[N];//ax + b
int par[N];
int find(int a){
	if(par[a] == a)return a;
	return par[a] = find(par[a]);
}
void merge(int a , int b){
	par[find(a)] = find(b);
}
void solve(){
	cin >> n >> m;
	iota(par , par + n + 1 , 0);
	for(int i = 0;i<=n;i++)mem[i] = {inf , inf};
	for(int i = 0;i<m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		graph[a].push_back({b , c});
		graph[b].push_back({a , c});
		merge(a,b);
	}
 
	int cnt_soln[n+1];
	memset(cnt_soln , 0 , sizeof(cnt_soln));
	double soln[n+1];
 
	set < int > roots;
	vector < int > components[n+1];
	for(int i = 1;i<=n;i++){
		roots.insert(find(i));
		components[find(i)].push_back(i);
	}
 
 
	queue < pair < int , pair < int , int > > > q;
	for(auto itr : roots){
		q.push({itr , {1 , 0}});		
	}
 
	while(sz(q)){
		int node = q.front().first;
		pair < int , int > eq = q.front().second;
		q.pop();
		if(mem[node] != pair < int , int >{inf , inf}){// check whether it matches or not
			if(mem[node].first == eq.first and mem[node].second != eq.second){
				cout << "NO" << endl;
				return;
			}
			else if(mem[node].first == eq.first){
				37;
			}
			else{
				if(cnt_soln[find(node)]){
					double mysoln = (double)(mem[node].second - eq.second) / (double)(eq.first - mem[node].first);
					if(abs(soln[find(node)] - mysoln) > EPS)cnt_soln[find(node)]++;
				}
				else{
					cnt_soln[find(node)]++;
					soln[find(node)] = (double)(mem[node].second - eq.second) / (double)(eq.first - mem[node].first);
				}
			}
		}
		else{
			mem[node] = eq;
			// cout << "node " << node << " : " << eq.first << " " << eq.second << endl;
			for(auto itr : graph[node]){
				q.push({itr.first , {-eq.first , itr.second - eq.second}});
			}
		}
	}
	double ans[n+1];
	for(auto itr : roots){
		if(cnt_soln[itr] > 1){
			cout << "NO" << endl;
			return;
		}
		else if(cnt_soln[itr] == 1){
			for(auto i : components[itr]){
				ans[i] = mem[i].first * soln[itr] + mem[i].second;
			}
		}
		else{
			auto check = [&](double x){
				double ret = 0;
				for(auto i : components[itr]){	
					ret += abs((double)mem[i].first * x + (double)mem[i].second);
				}	
				return ret;
			};
			double l = -INF , r = INF;
			while(abs(l - r) > EPS){
				double mid = (l + r) / 2;
				if(check(mid) < check(mid + EPS)){
					r = mid;				
				}
				else{
					l = mid + EPS;
				}
			}
			for(auto i : components[itr]){
				ans[i] = mem[i].first * l + mem[i].second;
			}
		}
	}
	cout << "YES" << endl;
	for(int i = 1;i<=n;i++)cout << fixed << setprecision(6) << ans[i] << " ";
	cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Compilation message

Graph.cpp: In function 'void solve()':
Graph.cpp:62:5: warning: statement has no effect [-Wunused-value]
   62 |     37;
      |     ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB answer = YES
2 Correct 1 ms 4956 KB answer = YES
3 Correct 1 ms 4956 KB answer = YES
4 Correct 1 ms 4956 KB answer = NO
5 Correct 1 ms 4956 KB answer = YES
6 Correct 1 ms 4956 KB answer = YES
7 Correct 1 ms 4956 KB answer = YES
8 Correct 1 ms 4952 KB answer = YES
9 Correct 1 ms 4956 KB answer = NO
10 Correct 1 ms 4956 KB answer = YES
11 Correct 1 ms 4956 KB answer = YES
12 Correct 1 ms 4956 KB answer = NO
13 Correct 1 ms 4952 KB answer = YES
14 Correct 1 ms 4952 KB answer = YES
15 Correct 1 ms 4952 KB answer = YES
16 Correct 1 ms 4952 KB answer = YES
17 Correct 1 ms 4956 KB answer = YES
18 Correct 1 ms 4956 KB answer = YES
19 Correct 1 ms 4980 KB answer = YES
20 Correct 1 ms 4956 KB answer = YES
21 Correct 1 ms 4956 KB answer = YES
22 Correct 1 ms 4956 KB answer = NO
23 Correct 1 ms 4968 KB answer = NO
24 Correct 2 ms 4952 KB answer = YES
25 Correct 1 ms 4952 KB answer = YES
26 Correct 1 ms 4956 KB answer = YES
27 Correct 1 ms 4956 KB answer = YES
28 Correct 1 ms 4952 KB answer = YES
29 Correct 1 ms 4952 KB answer = YES
30 Correct 1 ms 5152 KB answer = NO
31 Correct 1 ms 4956 KB answer = YES
32 Correct 1 ms 4956 KB answer = YES
33 Correct 2 ms 4956 KB answer = YES
34 Correct 1 ms 4956 KB answer = YES
35 Correct 1 ms 4952 KB answer = YES
36 Correct 1 ms 4956 KB answer = YES
37 Correct 1 ms 4952 KB answer = YES
38 Correct 2 ms 4956 KB answer = YES
39 Correct 2 ms 4952 KB answer = YES
40 Correct 2 ms 4956 KB answer = YES
41 Correct 1 ms 4956 KB answer = NO
42 Correct 2 ms 4956 KB answer = YES
43 Correct 2 ms 4956 KB answer = YES
44 Correct 2 ms 4956 KB answer = YES
45 Correct 2 ms 4952 KB answer = YES
46 Correct 2 ms 4956 KB answer = YES
47 Correct 2 ms 5020 KB answer = YES
48 Correct 2 ms 4956 KB answer = YES
49 Correct 10 ms 6488 KB answer = YES
50 Correct 8 ms 6492 KB answer = YES
51 Correct 12 ms 6532 KB answer = YES
52 Correct 6 ms 6236 KB answer = NO
53 Correct 2 ms 4956 KB answer = YES
54 Correct 3 ms 5372 KB answer = YES
55 Correct 7 ms 5724 KB answer = YES
56 Correct 10 ms 6492 KB answer = YES
57 Correct 11 ms 6492 KB answer = YES
58 Correct 9 ms 6236 KB answer = YES
59 Correct 7 ms 6236 KB answer = YES
60 Correct 10 ms 6492 KB answer = YES
61 Correct 5 ms 5724 KB answer = YES
62 Correct 44 ms 16988 KB answer = NO
63 Correct 76 ms 24956 KB answer = YES
64 Correct 43 ms 16976 KB answer = NO
65 Correct 58 ms 24764 KB answer = YES
66 Correct 3 ms 5208 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB answer = YES
2 Correct 1 ms 4956 KB answer = YES
3 Correct 1 ms 4956 KB answer = YES
4 Correct 1 ms 4956 KB answer = NO
5 Correct 1 ms 4956 KB answer = YES
6 Correct 1 ms 4956 KB answer = YES
7 Correct 1 ms 4956 KB answer = YES
8 Correct 1 ms 4952 KB answer = YES
9 Correct 1 ms 4956 KB answer = NO
10 Correct 1 ms 4956 KB answer = YES
11 Correct 1 ms 4956 KB answer = YES
12 Correct 1 ms 4956 KB answer = NO
13 Correct 1 ms 4952 KB answer = YES
14 Correct 1 ms 4952 KB answer = YES
15 Correct 1 ms 4952 KB answer = YES
16 Correct 1 ms 4952 KB answer = YES
17 Correct 1 ms 4956 KB answer = YES
18 Correct 1 ms 4956 KB answer = YES
19 Correct 1 ms 4980 KB answer = YES
20 Correct 1 ms 4956 KB answer = YES
21 Correct 1 ms 4956 KB answer = YES
22 Correct 1 ms 4956 KB answer = NO
23 Correct 1 ms 4968 KB answer = NO
24 Correct 2 ms 4952 KB answer = YES
25 Correct 1 ms 4952 KB answer = YES
26 Correct 1 ms 4956 KB answer = YES
27 Correct 1 ms 4956 KB answer = YES
28 Correct 1 ms 4952 KB answer = YES
29 Correct 1 ms 4952 KB answer = YES
30 Correct 1 ms 5152 KB answer = NO
31 Correct 1 ms 4956 KB answer = YES
32 Correct 1 ms 4956 KB answer = YES
33 Correct 2 ms 4956 KB answer = YES
34 Correct 1 ms 4956 KB answer = YES
35 Correct 1 ms 4952 KB answer = YES
36 Correct 1 ms 4956 KB answer = YES
37 Correct 1 ms 4952 KB answer = YES
38 Correct 2 ms 4956 KB answer = YES
39 Correct 2 ms 4952 KB answer = YES
40 Correct 2 ms 4956 KB answer = YES
41 Correct 1 ms 4956 KB answer = NO
42 Correct 2 ms 4956 KB answer = YES
43 Correct 2 ms 4956 KB answer = YES
44 Correct 2 ms 4956 KB answer = YES
45 Correct 2 ms 4952 KB answer = YES
46 Correct 2 ms 4956 KB answer = YES
47 Correct 2 ms 5020 KB answer = YES
48 Correct 2 ms 4956 KB answer = YES
49 Correct 10 ms 6488 KB answer = YES
50 Correct 8 ms 6492 KB answer = YES
51 Correct 12 ms 6532 KB answer = YES
52 Correct 6 ms 6236 KB answer = NO
53 Correct 2 ms 4956 KB answer = YES
54 Correct 3 ms 5372 KB answer = YES
55 Correct 7 ms 5724 KB answer = YES
56 Correct 10 ms 6492 KB answer = YES
57 Correct 11 ms 6492 KB answer = YES
58 Correct 9 ms 6236 KB answer = YES
59 Correct 7 ms 6236 KB answer = YES
60 Correct 10 ms 6492 KB answer = YES
61 Correct 5 ms 5724 KB answer = YES
62 Correct 44 ms 16988 KB answer = NO
63 Correct 76 ms 24956 KB answer = YES
64 Correct 43 ms 16976 KB answer = NO
65 Correct 58 ms 24764 KB answer = YES
66 Correct 3 ms 5208 KB answer = YES
67 Correct 97 ms 19380 KB answer = YES
68 Correct 85 ms 19136 KB answer = YES
69 Correct 64 ms 19120 KB answer = YES
70 Correct 101 ms 26832 KB answer = YES
71 Correct 65 ms 19144 KB answer = YES
72 Correct 103 ms 20224 KB answer = YES
73 Correct 89 ms 20120 KB answer = YES
74 Correct 51 ms 14508 KB answer = YES
75 Correct 22 ms 12740 KB answer = NO
76 Correct 12 ms 6748 KB answer = YES
77 Correct 26 ms 8664 KB answer = YES
78 Correct 42 ms 11532 KB answer = YES
79 Correct 89 ms 17916 KB answer = YES
80 Correct 65 ms 14284 KB answer = YES
81 Correct 46 ms 16844 KB answer = NO
82 Correct 88 ms 19264 KB answer = YES
83 Correct 87 ms 19912 KB answer = YES
84 Correct 120 ms 19904 KB answer = YES
85 Correct 90 ms 19404 KB answer = YES
86 Correct 71 ms 19368 KB answer = YES
87 Correct 41 ms 17512 KB answer = NO
88 Correct 100 ms 20024 KB answer = YES
89 Correct 98 ms 23348 KB answer = YES
90 Correct 100 ms 23376 KB answer = YES
91 Correct 107 ms 23488 KB answer = YES
92 Correct 40 ms 12572 KB answer = YES
93 Correct 40 ms 12560 KB answer = YES
94 Correct 47 ms 17352 KB answer = NO
95 Correct 62 ms 22560 KB answer = NO
96 Correct 151 ms 29128 KB answer = YES
97 Correct 30 ms 16844 KB answer = NO