oj.uz

답안 #802094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
802094 2023-08-02T09:50:38 Z parsadox2 Graph (BOI20_graph) C++14
100 / 100
 150 ms 27904 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5 + 10;
const long long inf = 1e18;
int n , m;
double ar[maxn] , x;
vector <pair<int , int>> adj[maxn];
pair<int , int> dis[maxn];
bool marked[maxn] , flg;
vector <int> trav;

void dfs(int v)
{
	marked[v] = true;
	trav.push_back(v);
	for(auto e : adj[v])
	{
		int u = e.first , w = e.second;
		if(!marked[u])
		{
			dis[u].first = w - dis[v].first;
			dis[u].second = -1 * dis[v].second;
			dfs(u);
		}
		else if(dis[u].second == dis[v].second)
		{
			flg = true;
			x = w - dis[u].first - dis[v].first;
			x = 1.0 * x / 2;
			if(dis[u].second == -1)
				x *= -1;
		}
		else if(dis[u].first + dis[v].first != w)
		{
			cout << "NO" << '\n';
			exit(0);
		}
	}
}

void solve(int v)
{
	flg = false;
	dis[v] = make_pair(0 , 1);
	trav.clear();
	dfs(v);
	if(flg)
	{
		for(auto u : trav)
		{
			ar[u] = dis[u].first;
			ar[u] += 1.0 * dis[u].second * x;
		}
		for(auto u : trav)  for(auto e : adj[u])  if(ar[u] + ar[e.first] != e.second)
		{
			cout << "NO" << '\n';
			exit(0);
		}
		return;
	}
	vector <int> ngt , pst;
	for(auto u : trav)
	{
		if(dis[u].second == -1)
			ngt.push_back(dis[u].first);
		else
			pst.push_back(dis[u].first);
	}
	vector <int> pngt , ppst;
	sort(ngt.begin() , ngt.end());
	sort(pst.begin() , pst.end());
	pngt.push_back(0);
	ppst.push_back(0);
	for(auto u : ngt)
		pngt.push_back(pngt.back() + u);
	for(auto u : pst)
		ppst.push_back(ppst.back() + u);
	int ili = trav.size();
	long long sum = inf;
	for(int i = -2 * ili ; i <= 2 * ili ; i++)
	{
		int tmp = lower_bound(pst.begin() , pst.end() , -i) - pst.begin();
		long long now = 0;
		now -= ppst[tmp];
		now -= tmp * i;
		now += (ppst.back() - ppst[tmp]);
		now += (ppst.size() - tmp) * i;
		int j = -i;
		tmp = lower_bound(ngt.begin() , ngt.end() , -j) - ngt.begin();
		now -= pngt[tmp];
		now -= tmp * j;
		now += (pngt.back() - pngt[tmp]);
		now += (pngt.size() - tmp) * j;
		if(now < sum)
		{
			sum = now;
			x = i;
		}
	}
	for(auto u : trav)
	{
		ar[u] = dis[u].first;
		ar[u] += 1.0 * dis[u].second * x;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++)
	{
		int v , u , w;  cin >> v >> u >> w;
		adj[v].push_back({u , w});
		adj[u].push_back({v , w});
	}
	for(int i = 1 ; i <= n ; i++)  if(!marked[i])
		solve(i);
	cout << "YES" << '\n';
	cout << setprecision(1) << fixed;
	for(int i = 1 ; i <= n ; i++)
		cout << ar[i] << " ";
	cout << '\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 1 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 1 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2816 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 1 ms 2684 KB answer = YES

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 1 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2816 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 1 ms 2684 KB answer = YES
37 Correct 2 ms 2688 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2772 KB answer = YES
40 Correct 2 ms 2696 KB answer = YES
41 Correct 2 ms 2772 KB answer = NO
42 Correct 2 ms 2820 KB answer = YES
43 Correct 2 ms 2772 KB answer = YES
44 Correct 2 ms 2772 KB answer = YES
45 Correct 2 ms 2792 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2776 KB answer = YES
48 Correct 2 ms 2772 KB answer = YES

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 1 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2816 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 1 ms 2684 KB answer = YES
37 Correct 2 ms 2688 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2772 KB answer = YES
40 Correct 2 ms 2696 KB answer = YES
41 Correct 2 ms 2772 KB answer = NO
42 Correct 2 ms 2820 KB answer = YES
43 Correct 2 ms 2772 KB answer = YES
44 Correct 2 ms 2772 KB answer = YES
45 Correct 2 ms 2792 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2776 KB answer = YES
48 Correct 2 ms 2772 KB answer = YES
49 Correct 8 ms 3924 KB answer = YES
50 Correct 8 ms 4108 KB answer = YES
51 Correct 11 ms 4240 KB answer = YES
52 Correct 4 ms 3412 KB answer = NO
53 Correct 2 ms 2772 KB answer = YES
54 Correct 3 ms 3028 KB answer = YES
55 Correct 7 ms 3340 KB answer = YES
56 Correct 8 ms 3868 KB answer = YES
57 Correct 8 ms 3668 KB answer = YES
58 Correct 7 ms 3668 KB answer = YES
59 Correct 9 ms 3540 KB answer = YES
60 Correct 8 ms 3808 KB answer = YES
61 Correct 4 ms 3168 KB answer = YES
62 Correct 43 ms 14184 KB answer = NO
63 Correct 66 ms 15056 KB answer = YES
64 Correct 57 ms 14924 KB answer = NO
65 Correct 60 ms 14980 KB answer = YES
66 Correct 3 ms 2900 KB answer = YES

Subtask #5
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 1 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2816 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 1 ms 2684 KB answer = YES
37 Correct 2 ms 2688 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2772 KB answer = YES
40 Correct 2 ms 2696 KB answer = YES
41 Correct 2 ms 2772 KB answer = NO
42 Correct 2 ms 2820 KB answer = YES
43 Correct 2 ms 2772 KB answer = YES
44 Correct 2 ms 2772 KB answer = YES
45 Correct 2 ms 2792 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2776 KB answer = YES
48 Correct 2 ms 2772 KB answer = YES
49 Correct 8 ms 3924 KB answer = YES
50 Correct 8 ms 4108 KB answer = YES
51 Correct 11 ms 4240 KB answer = YES
52 Correct 4 ms 3412 KB answer = NO
53 Correct 2 ms 2772 KB answer = YES
54 Correct 3 ms 3028 KB answer = YES
55 Correct 7 ms 3340 KB answer = YES
56 Correct 8 ms 3868 KB answer = YES
57 Correct 8 ms 3668 KB answer = YES
58 Correct 7 ms 3668 KB answer = YES
59 Correct 9 ms 3540 KB answer = YES
60 Correct 8 ms 3808 KB answer = YES
61 Correct 4 ms 3168 KB answer = YES
62 Correct 43 ms 14184 KB answer = NO
63 Correct 66 ms 15056 KB answer = YES
64 Correct 57 ms 14924 KB answer = NO
65 Correct 60 ms 14980 KB answer = YES
66 Correct 3 ms 2900 KB answer = YES
67 Correct 87 ms 22032 KB answer = YES
68 Correct 87 ms 22008 KB answer = YES
69 Correct 67 ms 20180 KB answer = YES
70 Correct 130 ms 27904 KB answer = YES
71 Correct 66 ms 20288 KB answer = YES
72 Correct 86 ms 14656 KB answer = YES
73 Correct 94 ms 12912 KB answer = YES
74 Correct 61 ms 13224 KB answer = YES
75 Correct 19 ms 10024 KB answer = NO
76 Correct 10 ms 4180 KB answer = YES
77 Correct 20 ms 5640 KB answer = YES
78 Correct 36 ms 7852 KB answer = YES
79 Correct 84 ms 13028 KB answer = YES
80 Correct 78 ms 14092 KB answer = YES
81 Correct 44 ms 15292 KB answer = NO
82 Correct 91 ms 19656 KB answer = YES
83 Correct 116 ms 21040 KB answer = YES
84 Correct 150 ms 22516 KB answer = YES
85 Correct 103 ms 21948 KB answer = YES
86 Correct 67 ms 20360 KB answer = YES
87 Correct 58 ms 14244 KB answer = NO
88 Correct 106 ms 15996 KB answer = YES
89 Correct 76 ms 11568 KB answer = YES
90 Correct 60 ms 11436 KB answer = YES
91 Correct 70 ms 12084 KB answer = YES
92 Correct 32 ms 7808 KB answer = YES
93 Correct 32 ms 7816 KB answer = YES
94 Correct 48 ms 19600 KB answer = NO
95 Correct 31 ms 11600 KB answer = NO
96 Correct 128 ms 24168 KB answer = YES
97 Correct 28 ms 19008 KB answer = NO