oj.uz

Submission #973905

# Submission time Handle Problem Language Result Execution time Memory
973905 2024-05-02T12:39:30 Z NotLinux Graph (BOI20_graph) C++17
0 / 100
 2 ms 4956 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.0000001;
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);
	}
	set < int > roots;
	for(int i = 1;i<=n;i++){
		roots.insert(find(i));
	}
	queue < pair < int , pair < int , int > > > q;
	for(auto itr : roots){
		q.push({itr , {1 , 0}});		
	}
	set < double > possible;
	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{
				possible.insert((double)(mem[node].second - eq.second) / (double)(eq.first - mem[node].first));
			}
		}
		else{
			mem[node] = eq;
			// cout << node << " : " << eq.first << " , " << eq.second << endl;;
			for(auto itr : graph[node]){
				q.push({itr.first , {-eq.first , itr.second - eq.second}});
			}
		}
	}
	// cout << "possible : ";for(auto itr : possible)cout << itr << " ";cout << endl;
	auto answer = [&](double x){
		cout << "YES" << endl;
		for(int i = 1;i<=n;i++){
			cout << fixed << setprecision(6) << (double)mem[i].first * x + (double)mem[i].second << ' ';
		}
		cout << endl;
	};
	if(sz(possible) > 1){
		cout << "NO" << endl;
		return;
	}
	else if(sz(possible) == 1){
		// double ret = 0 , x = *possible.begin();
		// for(int i = 1;i<=n;i++){
		// 	ret += abs((double)mem[i].first * x + (double)mem[i].second);
		// }
		// cout << ret << endl;
		answer(*possible.begin());
	}
	else{
		// binary search ?
		auto check = [&](double x){
			double ret = 0;
			for(int i = 1;i<=n;i++){
				ret += abs((double)mem[i].first * x + (double)mem[i].second);
			}	
			return ret;
		};
		double l = 0 , r = INF;
		while(abs(l - r) > EPS){
			double mid = (l + r) / 2;
			if(check(mid) < check(mid + EPS)){
				r = mid;				
			}
			else{
				l = mid + EPS;
			}
		}
		// cout << check(l) << endl;
		answer(l);
	}
}
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:53:5: warning: statement has no effect [-Wunused-value]
   53 |     37;
      |     ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB answer = YES
2 Correct 2 ms 4952 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 2 ms 4952 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 4952 KB answer = YES
11 Correct 1 ms 4792 KB answer = YES
12 Correct 1 ms 4956 KB answer = NO
13 Correct 1 ms 4956 KB answer = YES
14 Correct 1 ms 4956 KB answer = YES
15 Correct 1 ms 4956 KB answer = YES
16 Correct 1 ms 4956 KB answer = YES
17 Correct 1 ms 4956 KB answer = YES
18 Correct 1 ms 4956 KB answer = YES
19 Incorrect 1 ms 4956 KB jury has the better answer: jans = YES, pans = NO
20 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB answer = YES
2 Correct 2 ms 4952 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 2 ms 4952 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 4952 KB answer = YES
11 Correct 1 ms 4792 KB answer = YES
12 Correct 1 ms 4956 KB answer = NO
13 Correct 1 ms 4956 KB answer = YES
14 Correct 1 ms 4956 KB answer = YES
15 Correct 1 ms 4956 KB answer = YES
16 Correct 1 ms 4956 KB answer = YES
17 Correct 1 ms 4956 KB answer = YES
18 Correct 1 ms 4956 KB answer = YES
19 Incorrect 1 ms 4956 KB jury has the better answer: jans = YES, pans = NO
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB answer = YES
2 Correct 2 ms 4952 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 2 ms 4952 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 4952 KB answer = YES
11 Correct 1 ms 4792 KB answer = YES
12 Correct 1 ms 4956 KB answer = NO
13 Correct 1 ms 4956 KB answer = YES
14 Correct 1 ms 4956 KB answer = YES
15 Correct 1 ms 4956 KB answer = YES
16 Correct 1 ms 4956 KB answer = YES
17 Correct 1 ms 4956 KB answer = YES
18 Correct 1 ms 4956 KB answer = YES
19 Incorrect 1 ms 4956 KB jury has the better answer: jans = YES, pans = NO
20 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB answer = YES
2 Correct 2 ms 4952 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 2 ms 4952 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 4952 KB answer = YES
11 Correct 1 ms 4792 KB answer = YES
12 Correct 1 ms 4956 KB answer = NO
13 Correct 1 ms 4956 KB answer = YES
14 Correct 1 ms 4956 KB answer = YES
15 Correct 1 ms 4956 KB answer = YES
16 Correct 1 ms 4956 KB answer = YES
17 Correct 1 ms 4956 KB answer = YES
18 Correct 1 ms 4956 KB answer = YES
19 Incorrect 1 ms 4956 KB jury has the better answer: jans = YES, pans = NO
20 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB answer = YES
2 Correct 2 ms 4952 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 2 ms 4952 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 4952 KB answer = YES
11 Correct 1 ms 4792 KB answer = YES
12 Correct 1 ms 4956 KB answer = NO
13 Correct 1 ms 4956 KB answer = YES
14 Correct 1 ms 4956 KB answer = YES
15 Correct 1 ms 4956 KB answer = YES
16 Correct 1 ms 4956 KB answer = YES
17 Correct 1 ms 4956 KB answer = YES
18 Correct 1 ms 4956 KB answer = YES
19 Incorrect 1 ms 4956 KB jury has the better answer: jans = YES, pans = NO
20 Halted 0 ms 0 KB -