Submission #287845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
287845	2020-09-01T04:16:30 Z	nandonathaniel	Graph (BOI20_graph)	C++14	100 / 100	184 ms	14304 KB

Graph

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=100005,INF=1e9,LOG=90;
pii nilai[MAXN];
vector<pii> adj[MAXN];
double point[MAXN];

void gagal(){
	cout << "NO\n";
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,m,u,v,w;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++){
		nilai[i].first=INF;
		nilai[i].second=INF;
	}
	for(int i=1;i<=n;i++){
		if(nilai[i].first!=INF)continue;
		//linear equation
		vector<int> V;
		queue<int> Q;
		Q.push(i);
		nilai[i]={1,0};   //x and const
		double X=(double)INF;
		while(!Q.empty()){
			int now=Q.front();
			V.push_back(now);
			Q.pop();
			for(auto nxt : adj[now]){
				if(nilai[nxt.first]==make_pair(INF,INF)){
					nilai[nxt.first]={-nilai[now].first,nxt.second-nilai[now].second};
					Q.push(nxt.first);
				}
				else{
					if(nilai[now].first+nilai[nxt.first].first==0 && nilai[now].second+nilai[nxt.first].second!=nxt.second)gagal();
					if(nilai[now].first+nilai[nxt.first].first!=0){
						double xnow=((double)nxt.second-((double)nilai[now].second+(double)nilai[nxt.first].second))/((double)nilai[now].first+(double)nilai[nxt.first].first);
						if(X==INF)X=xnow;
						else if(xnow!=X)gagal();
					}
				}
			}
		}
		if(X!=INF){
			for(auto isi : V)point[isi]=X*(double)nilai[isi].first+(double)nilai[isi].second;
			continue;
		}
		vector<int> candidate;
		for(auto isi : V){
			if(nilai[isi].first==-1)candidate.push_back(nilai[isi].second);
			else candidate.push_back(-nilai[isi].second);
		}
		sort(candidate.begin(),candidate.end());
		//x yang membuat sigma(ax+b) terkecil adalah median dari pembuat nol semua persamaan mutlak
		X=candidate[V.size()/2];
		if(V.size()%2==0)X=(double)(X+candidate[V.size()/2-1])/2.0;
		for(auto isi : V)point[isi]=X*(double)nilai[isi].first+(double)nilai[isi].second;
	}
	cout << "YES\n";
	for(int i=1;i<=n;i++){
		cout << fixed << setprecision(6) << point[i];
		if(i<n)cout << ' ';
		else cout << '\n';
	}
	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	2 ms	2688 KB	answer = YES
36	Correct	2 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	2 ms	2688 KB	answer = YES
36	Correct	2 ms	2688 KB	answer = YES
37	Correct	2 ms	2688 KB	answer = YES
38	Correct	2 ms	2688 KB	answer = YES
39	Correct	3 ms	2816 KB	answer = YES
40	Correct	3 ms	2816 KB	answer = YES
41	Correct	2 ms	2688 KB	answer = NO
42	Correct	3 ms	2816 KB	answer = YES
43	Correct	3 ms	2816 KB	answer = YES
44	Correct	3 ms	2816 KB	answer = YES
45	Correct	3 ms	2816 KB	answer = YES
46	Correct	3 ms	2816 KB	answer = YES
47	Correct	3 ms	2816 KB	answer = YES
48	Correct	3 ms	2816 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	2 ms	2688 KB	answer = YES
36	Correct	2 ms	2688 KB	answer = YES
37	Correct	2 ms	2688 KB	answer = YES
38	Correct	2 ms	2688 KB	answer = YES
39	Correct	3 ms	2816 KB	answer = YES
40	Correct	3 ms	2816 KB	answer = YES
41	Correct	2 ms	2688 KB	answer = NO
42	Correct	3 ms	2816 KB	answer = YES
43	Correct	3 ms	2816 KB	answer = YES
44	Correct	3 ms	2816 KB	answer = YES
45	Correct	3 ms	2816 KB	answer = YES
46	Correct	3 ms	2816 KB	answer = YES
47	Correct	3 ms	2816 KB	answer = YES
48	Correct	3 ms	2816 KB	answer = YES
49	Correct	11 ms	3540 KB	answer = YES
50	Correct	11 ms	3456 KB	answer = YES
51	Correct	12 ms	3508 KB	answer = YES
52	Correct	6 ms	3200 KB	answer = NO
53	Correct	3 ms	2816 KB	answer = YES
54	Correct	4 ms	2944 KB	answer = YES
55	Correct	7 ms	3200 KB	answer = YES
56	Correct	11 ms	3508 KB	answer = YES
57	Correct	12 ms	3456 KB	answer = YES
58	Correct	10 ms	3456 KB	answer = YES
59	Correct	10 ms	3456 KB	answer = YES
60	Correct	11 ms	3584 KB	answer = YES
61	Correct	6 ms	3072 KB	answer = YES
62	Correct	68 ms	9720 KB	answer = NO
63	Correct	73 ms	9848 KB	answer = YES
64	Correct	72 ms	9720 KB	answer = NO
65	Correct	74 ms	9848 KB	answer = YES
66	Correct	4 ms	2816 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	2 ms	2688 KB	answer = YES
36	Correct	2 ms	2688 KB	answer = YES
37	Correct	2 ms	2688 KB	answer = YES
38	Correct	2 ms	2688 KB	answer = YES
39	Correct	3 ms	2816 KB	answer = YES
40	Correct	3 ms	2816 KB	answer = YES
41	Correct	2 ms	2688 KB	answer = NO
42	Correct	3 ms	2816 KB	answer = YES
43	Correct	3 ms	2816 KB	answer = YES
44	Correct	3 ms	2816 KB	answer = YES
45	Correct	3 ms	2816 KB	answer = YES
46	Correct	3 ms	2816 KB	answer = YES
47	Correct	3 ms	2816 KB	answer = YES
48	Correct	3 ms	2816 KB	answer = YES
49	Correct	11 ms	3540 KB	answer = YES
50	Correct	11 ms	3456 KB	answer = YES
51	Correct	12 ms	3508 KB	answer = YES
52	Correct	6 ms	3200 KB	answer = NO
53	Correct	3 ms	2816 KB	answer = YES
54	Correct	4 ms	2944 KB	answer = YES
55	Correct	7 ms	3200 KB	answer = YES
56	Correct	11 ms	3508 KB	answer = YES
57	Correct	12 ms	3456 KB	answer = YES
58	Correct	10 ms	3456 KB	answer = YES
59	Correct	10 ms	3456 KB	answer = YES
60	Correct	11 ms	3584 KB	answer = YES
61	Correct	6 ms	3072 KB	answer = YES
62	Correct	68 ms	9720 KB	answer = NO
63	Correct	73 ms	9848 KB	answer = YES
64	Correct	72 ms	9720 KB	answer = NO
65	Correct	74 ms	9848 KB	answer = YES
66	Correct	4 ms	2816 KB	answer = YES
67	Correct	98 ms	9940 KB	answer = YES
68	Correct	91 ms	9808 KB	answer = YES
69	Correct	84 ms	9944 KB	answer = YES
70	Correct	120 ms	14296 KB	answer = YES
71	Correct	86 ms	9816 KB	answer = YES
72	Correct	116 ms	10624 KB	answer = YES
73	Correct	109 ms	10456 KB	answer = YES
74	Correct	70 ms	7440 KB	answer = YES
75	Correct	30 ms	6528 KB	answer = NO
76	Correct	13 ms	3756 KB	answer = YES
77	Correct	25 ms	4736 KB	answer = YES
78	Correct	43 ms	6072 KB	answer = YES
79	Correct	90 ms	9364 KB	answer = YES
80	Correct	72 ms	7400 KB	answer = YES
81	Correct	51 ms	8184 KB	answer = NO
82	Correct	109 ms	9948 KB	answer = YES
83	Correct	132 ms	9944 KB	answer = YES
84	Correct	141 ms	9936 KB	answer = YES
85	Correct	105 ms	9936 KB	answer = YES
86	Correct	101 ms	9944 KB	answer = YES
87	Correct	66 ms	8952 KB	answer = NO
88	Correct	137 ms	9904 KB	answer = YES
89	Correct	111 ms	9592 KB	answer = YES
90	Correct	109 ms	9592 KB	answer = YES
91	Correct	124 ms	9720 KB	answer = YES
92	Correct	52 ms	6708 KB	answer = YES
93	Correct	50 ms	6704 KB	answer = YES
94	Correct	71 ms	8564 KB	answer = NO
95	Correct	59 ms	8696 KB	answer = NO
96	Correct	184 ms	14304 KB	answer = YES
97	Correct	39 ms	8564 KB	answer = NO

Submission #287845

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 12.0 / 12.0

Subtask #3 17.0 / 17.0

Subtask #4 24.0 / 24.0

Subtask #5 42.0 / 42.0

Subtask #1
5.0 / 5.0

Subtask #2
12.0 / 12.0

Subtask #3
17.0 / 17.0

Subtask #4
24.0 / 24.0

Subtask #5
42.0 / 42.0