oj.uz

Submission #257267

# Submission time Handle Problem Language Result Execution time Memory
257267 2020-08-04T03:04:15 Z maximath_1 Graph (BOI20_graph) C++11
100 / 100
 449 ms 45576 KB 
/*
	* BOI 2020 2A: Graph
	* Set a variable x on one vertex
	* Express values of all vertices in terms of x
	* If there is colliding information, no solution
	* Else, take the minimum of the sum
	* Ah also do that for every connected component :|
*/
//I have started to include headers one by one
//Because I need to wait like a minute for it to compile in my pc
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <deque>
#include <iostream>
#include <limits>
#include <string>
#include <tuple>
#include <iterator>
#include <complex>
#include <random>
#include <iomanip>
using namespace std;
 
#define ll long long
#define ld long double
const ll inf = 1e18;
const ld eps = 1e-6;
struct eq{
	ld m, c; //mx + c
	eq(){}
	eq(ld a, ld b) : m(a) , c(b) {}
 
	eq& operator+=(const eq&rhs){m += rhs.m, c += rhs.c; return *this;}
	eq& operator-=(const eq&rhs){m -= rhs.m, c -= rhs.c; return *this;}
	friend eq operator+(eq a, const eq& b) {return a += b;}
	friend eq operator-(eq a, const eq& b) {return a -= b;}
};
 
ld solv(eq a, eq b){
	//a.m x + a.c = b.m x + b.c
	if(abs(a.m - b.m) < eps){
		if(abs(a.c - b.c) > eps) return -(ld)inf; //no solution
		else return (ld)inf; //inf many solution
	}
	return (ld)(b.c - a.c) / (ld)(a.m - b.m); //one solution
}
ld f(eq a, ld x){
	return (ld)a.m * x + (ld)a.c;
}
 
int n, m;
eq nod[100005];
ld x; //var
vector<pair<int, int> > adj[100005];
bitset<100005> vis;
vector<int> cc;
ld ans[100005];
bool x_found = false, fail_condition = false;
 
void dfs(int nw, int bf, eq cr){
	if(fail_condition) return; //pretty much self explanatory
	if(vis[nw]){
		//compare the existing equation with the new one
		ld get = solv(nod[nw], cr);
		if(abs(get) < eps) get = 0.0; //you know those -0.0? yea to deal with that
		if(abs(get + inf) < eps) fail_condition = true; //no sol
		else if(abs(get - (ld)inf) > eps){
			if(x_found && abs(x - get) > eps) fail_condition = true; //conflicting x val
			else{
				x = get; x_found = true; //x found
			}
		}
		return;
	}
 
	cc.push_back(nw);
	nod[nw] = cr; vis[nw] = 1;
	for(pair<int, int> nx : adj[nw]) if(nx.first != bf){
		eq nex(0, nx.second);
		nex -= nod[nw];
		dfs(nx.first, nw, nex);
	}
	return;
}
 
unordered_map<ll, int> viss;
ll hash_(int a, int b){
	return a * 200005ll + b;
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(10);
 
	//read
	cin >> n >> m;
	for(int u, v, w, i = 0; i < m; i ++){
		cin >> u >> v >> w;
		if(viss[hash_(u, v)]){
			if(viss[hash_(u, v)] == w) continue;
			cout << "NO\n";
			return 0;
		}
		viss[hash_(u, v)] = viss[hash_(v, u)] = w;
		adj[u].push_back({v, w});
		if(u != v) adj[v].push_back({u, w});
	}
 
	//solve
	vis = 0;
	for(int i = 1; i <= n; i ++) if(!vis[i]){
		cc.clear(); x_found = false;
		dfs(i, i, eq(1, 0));
		if(fail_condition) break;
		if(!x_found){
			//check annoying self-loops >:V
			bool flag = false;
			for(int j : cc){
				if(viss[hash_(j, j)]){
					x = solv(nod[j], eq(0, (ld)viss[hash_(j, j)] / 2.0));
					flag = true; break;
				}
			}
			if(!flag){
				//This point, you can do slope trick, ternary search or whatever
				//Easiest is to take the median of the values
				vector<ld> values;
				for(int j : cc) values.push_back(solv(nod[j], eq(0, 0)));
				sort(values.begin(), values.end());
				if(values.size() % 2 == 0)
					x = values[values.size() / 2] + values[values.size() / 2 - 1];
				else
					x = values[values.size() / 2] + values[values.size() / 2];
				x /= (ld)2.0;
			}
		}
		for(int j : cc) ans[j] = f(nod[j], x);
	}
 
	for(int i = 1; i <= n; i ++){
		for(pair<int, int> j : adj[i]){
			if(abs((ld)ans[i] + (ld)ans[j.first] - (ld)j.second) > eps){
				printf("NO\n"); return 0;
			}
		}
	}
 
	//print
	if(fail_condition) cout << "NO\n";
	else{
		cout << "YES\n";
		for(int i = 1; i <= n; i ++)
			cout << ans[i] << " ";
	}
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB answer = YES
2 Correct 2 ms 2688 KB answer = YES
3 Correct 2 ms 2688 KB answer = YES
4 Correct 2 ms 2688 KB answer = NO
5 Correct 2 ms 2688 KB answer = YES
6 Correct 2 ms 2688 KB answer = YES
7 Correct 2 ms 2688 KB answer = YES
8 Correct 2 ms 2688 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2688 KB answer = YES
11 Correct 2 ms 2688 KB answer = YES
12 Correct 2 ms 2688 KB answer = NO
13 Correct 2 ms 2688 KB answer = YES
14 Correct 2 ms 2688 KB answer = YES
15 Correct 2 ms 2688 KB answer = YES
16 Correct 2 ms 2688 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2688 KB answer = YES
19 Correct 2 ms 2688 KB answer = YES
20 Correct 2 ms 2688 KB answer = YES
21 Correct 2 ms 2688 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2688 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2688 KB answer = YES
27 Correct 2 ms 2688 KB answer = YES
28 Correct 2 ms 2688 KB answer = YES
29 Correct 2 ms 2688 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2688 KB answer = YES
32 Correct 3 ms 2688 KB answer = YES
33 Correct 2 ms 2688 KB answer = YES
34 Correct 2 ms 2688 KB answer = YES
35 Correct 3 ms 2688 KB answer = YES
36 Correct 3 ms 2688 KB answer = YES
37 Correct 2 ms 2816 KB answer = YES
38 Correct 2 ms 2688 KB answer = YES
39 Correct 3 ms 2944 KB answer = YES
40 Correct 3 ms 2944 KB answer = YES
41 Correct 2 ms 2944 KB answer = NO
42 Correct 3 ms 3072 KB answer = YES
43 Correct 4 ms 2944 KB answer = YES
44 Correct 3 ms 2944 KB answer = YES
45 Correct 3 ms 2944 KB answer = YES
46 Correct 3 ms 2816 KB answer = YES
47 Correct 3 ms 2944 KB answer = YES
48 Correct 4 ms 2944 KB answer = YES
49 Correct 21 ms 5544 KB answer = YES
50 Correct 19 ms 5376 KB answer = YES
51 Correct 18 ms 6036 KB answer = YES
52 Correct 9 ms 4432 KB answer = NO
53 Correct 3 ms 2944 KB answer = YES
54 Correct 6 ms 3456 KB answer = YES
55 Correct 9 ms 4144 KB answer = YES
56 Correct 18 ms 5396 KB answer = YES
57 Correct 24 ms 5168 KB answer = YES
58 Correct 16 ms 5168 KB answer = YES
59 Correct 14 ms 4480 KB answer = YES
60 Correct 19 ms 5296 KB answer = YES
61 Correct 9 ms 3712 KB answer = YES
62 Correct 11 ms 4512 KB answer = NO
63 Correct 314 ms 26888 KB answer = YES
64 Correct 259 ms 26760 KB answer = NO
65 Correct 272 ms 26884 KB answer = YES
66 Correct 5 ms 3200 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB answer = YES
2 Correct 2 ms 2688 KB answer = YES
3 Correct 2 ms 2688 KB answer = YES
4 Correct 2 ms 2688 KB answer = NO
5 Correct 2 ms 2688 KB answer = YES
6 Correct 2 ms 2688 KB answer = YES
7 Correct 2 ms 2688 KB answer = YES
8 Correct 2 ms 2688 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2688 KB answer = YES
11 Correct 2 ms 2688 KB answer = YES
12 Correct 2 ms 2688 KB answer = NO
13 Correct 2 ms 2688 KB answer = YES
14 Correct 2 ms 2688 KB answer = YES
15 Correct 2 ms 2688 KB answer = YES
16 Correct 2 ms 2688 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2688 KB answer = YES
19 Correct 2 ms 2688 KB answer = YES
20 Correct 2 ms 2688 KB answer = YES
21 Correct 2 ms 2688 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2688 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2688 KB answer = YES
27 Correct 2 ms 2688 KB answer = YES
28 Correct 2 ms 2688 KB answer = YES
29 Correct 2 ms 2688 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2688 KB answer = YES
32 Correct 3 ms 2688 KB answer = YES
33 Correct 2 ms 2688 KB answer = YES
34 Correct 2 ms 2688 KB answer = YES
35 Correct 3 ms 2688 KB answer = YES
36 Correct 3 ms 2688 KB answer = YES
37 Correct 2 ms 2816 KB answer = YES
38 Correct 2 ms 2688 KB answer = YES
39 Correct 3 ms 2944 KB answer = YES
40 Correct 3 ms 2944 KB answer = YES
41 Correct 2 ms 2944 KB answer = NO
42 Correct 3 ms 3072 KB answer = YES
43 Correct 4 ms 2944 KB answer = YES
44 Correct 3 ms 2944 KB answer = YES
45 Correct 3 ms 2944 KB answer = YES
46 Correct 3 ms 2816 KB answer = YES
47 Correct 3 ms 2944 KB answer = YES
48 Correct 4 ms 2944 KB answer = YES
49 Correct 21 ms 5544 KB answer = YES
50 Correct 19 ms 5376 KB answer = YES
51 Correct 18 ms 6036 KB answer = YES
52 Correct 9 ms 4432 KB answer = NO
53 Correct 3 ms 2944 KB answer = YES
54 Correct 6 ms 3456 KB answer = YES
55 Correct 9 ms 4144 KB answer = YES
56 Correct 18 ms 5396 KB answer = YES
57 Correct 24 ms 5168 KB answer = YES
58 Correct 16 ms 5168 KB answer = YES
59 Correct 14 ms 4480 KB answer = YES
60 Correct 19 ms 5296 KB answer = YES
61 Correct 9 ms 3712 KB answer = YES
62 Correct 11 ms 4512 KB answer = NO
63 Correct 314 ms 26888 KB answer = YES
64 Correct 259 ms 26760 KB answer = NO
65 Correct 272 ms 26884 KB answer = YES
66 Correct 5 ms 3200 KB answer = YES
67 Correct 170 ms 39656 KB answer = YES
68 Correct 155 ms 39648 KB answer = YES
69 Correct 141 ms 33080 KB answer = YES
70 Correct 210 ms 45576 KB answer = YES
71 Correct 137 ms 33152 KB answer = YES
72 Correct 278 ms 29160 KB answer = YES
73 Correct 219 ms 22712 KB answer = YES
74 Correct 125 ms 21560 KB answer = YES
75 Correct 77 ms 16572 KB answer = NO
76 Correct 20 ms 5868 KB answer = YES
77 Correct 44 ms 9220 KB answer = YES
78 Correct 90 ms 14488 KB answer = YES
79 Correct 239 ms 26188 KB answer = YES
80 Correct 164 ms 24508 KB answer = YES
81 Correct 130 ms 24888 KB answer = NO
82 Correct 248 ms 32184 KB answer = YES
83 Correct 252 ms 33204 KB answer = YES
84 Correct 313 ms 39780 KB answer = YES
85 Correct 170 ms 39652 KB answer = YES
86 Correct 144 ms 33212 KB answer = YES
87 Correct 183 ms 23224 KB answer = NO
88 Correct 271 ms 26680 KB answer = YES
89 Correct 246 ms 21176 KB answer = YES
90 Correct 241 ms 21180 KB answer = YES
91 Correct 250 ms 21176 KB answer = YES
92 Correct 82 ms 12808 KB answer = YES
93 Correct 85 ms 12676 KB answer = YES
94 Correct 162 ms 30140 KB answer = NO
95 Correct 129 ms 20024 KB answer = NO
96 Correct 449 ms 40456 KB answer = YES
97 Correct 78 ms 30264 KB answer = NO