oj.uz

답안 #443998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443998 2021-07-12T20:19:43 Z aryan12 Pipes (BOI13_pipes) C++17
74.0741 / 100
 219 ms 29456 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 5;
int change[N], result[N];
vector<pair<int, int> > g[N];
int edgeChange[N], temp[N];
bool vis[N];
int n, m, bruh;
vector<int> cycle, cycle_edges;

void dfs(int node, int par, int edgeNum) {
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i].first != par) {
			dfs(g[node][i].first, node, g[node][i].second);
		}
	}
	int netWithParent = change[node] - result[node];
	if(par != -1) {
		result[node] += netWithParent;
		edgeChange[edgeNum] = netWithParent;
		result[par] += netWithParent;
	}
}

void Tree() {
	dfs(1, -1, -1);
	if(result[1] != change[1]) {
		cout << "0\n";
		return;
	}
	for(int i = 1; i <= m; i++) {
		cout << edgeChange[i] * 2 << "\n";
	}
}

void dfs1(int node, int par) {
	vis[node] = true;
	cycle.push_back(node);
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i].first == par) {
			continue;
		}
		if(!vis[g[node][i].first]) {
			cycle_edges.push_back(g[node][i].second);
			dfs1(g[node][i].first, node);
		}
		if(g[node][i].first == bruh) {
			cycle_edges.push_back(g[node][i].second);
		}
	}
}

void Solve() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> change[i];
	}
	for(int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(make_pair(v, i));
		g[v].push_back(make_pair(u, i));
	}
	if(m == n - 1) {
		Tree();
		return;
	}
	if(m > n) {
		cout << "0\n";
		return;
	}
	int cnt = 0;
	queue<int> q;
	for(int i = 1; i <= n; i++) {
		vis[i] = false;
		temp[i] = g[i].size();
		if(temp[i] == 1) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		int node = q.front();
		vis[node] = true;
		q.pop();
		cnt++;
		for(int i = 0; i < g[node].size(); i++) {
			if(!vis[g[node][i].first]) {
				temp[g[node][i].first]--;
				if(temp[g[node][i].first] == 1) {
					q.push(g[node][i].first);
				}
				int netChange = change[node] - result[node];
				edgeChange[g[node][i].second] = netChange;
				result[node] += netChange;
				result[g[node][i].first] += netChange;
			}
		}
	}
	if((n - cnt) % 2 == 0) {
		cout << "0\n";
		return;
	}
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			bruh = i;
			dfs1(i, -1);
		}
	}
	/*for(int i = 1; i <= n; i++) {
		cout << "change[i] = " << change[i] << ", result[i] = " << result[i] << "\n";
	}*/
	int sum = 0;
	for(int i = 0; i < cycle.size(); i++) {
		if(i % 2 == 0) {
			sum += (change[cycle[i]] - result[cycle[i]]);
		}
		else {
			sum -= (change[cycle[i]] - result[cycle[i]]);
		}
	}
	if(sum % 2 == 1) {
		cout << "0\n";
		return;
	}
	/*cout << "sum = " << sum << "\n";
	edgeChange[cycle_edges[0]] = sum / 2;
	for(int i = 0; i < cycle_edges.size(); i++) {
		cout << cycle_edges[i] << " ";
	}
	cout << "\n";
	for(int i = 0; i < cycle.size(); i++) {
		cout << cycle[i] << " ";
	}
	cout << "\n";*/
	for(int i = 1; i < cycle_edges.size(); i++) {
		edgeChange[cycle_edges[i]] = change[cycle[i - 1]] - result[cycle[i - 1]] - edgeChange[cycle_edges[i - 1]];
	}
	for(int i = 1; i <= m; i++) {
		cout << edgeChange[i] * 2 << "\n";
	}
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(long long int, long long int, long long int)':
pipes.cpp:16:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
pipes.cpp: In function 'void dfs1(long long int, long long int)':
pipes.cpp:43:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
pipes.cpp: In function 'void Solve()':
pipes.cpp:90:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for(int i = 0; i < g[node].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
pipes.cpp:117:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(int i = 0; i < cycle.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
pipes.cpp:139:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for(int i = 1; i < cycle_edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 68 ms 10452 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2672 KB Output is correct
12 Correct 2 ms 2764 KB Output is correct
13 Correct 52 ms 8868 KB Output is correct
14 Correct 68 ms 10040 KB Output is correct
15 Correct 72 ms 10576 KB Output is correct
16 Correct 59 ms 9284 KB Output is correct
17 Correct 68 ms 10432 KB Output is correct
18 Correct 69 ms 10528 KB Output is correct
19 Correct 76 ms 13620 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2764 KB Output is correct
22 Correct 72 ms 10508 KB Output is correct
23 Correct 53 ms 8932 KB Output is correct
24 Correct 67 ms 10508 KB Output is correct
25 Correct 56 ms 9184 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Correct 57 ms 10812 KB Output is correct
4 Correct 48 ms 8560 KB Output is correct
5 Correct 49 ms 8396 KB Output is correct
6 Correct 219 ms 29456 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Incorrect 3 ms 2636 KB Output isn't correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Incorrect 2 ms 2636 KB Output isn't correct
15 Incorrect 2 ms 2764 KB Output isn't correct
16 Incorrect 2 ms 2764 KB Output isn't correct
17 Correct 2 ms 2764 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 3 ms 2844 KB Output is correct
22 Incorrect 2 ms 2764 KB Output isn't correct
23 Incorrect 68 ms 14964 KB Output isn't correct
24 Incorrect 80 ms 16740 KB Output isn't correct
25 Correct 62 ms 10820 KB Output is correct
26 Correct 49 ms 8580 KB Output is correct
27 Correct 51 ms 8508 KB Output is correct
28 Correct 53 ms 8896 KB Output is correct
29 Correct 173 ms 24048 KB Output is correct
30 Incorrect 77 ms 15600 KB Output isn't correct
31 Incorrect 82 ms 19852 KB Output isn't correct
32 Incorrect 80 ms 13356 KB Output isn't correct
33 Correct 59 ms 11272 KB Output is correct
34 Correct 50 ms 8536 KB Output is correct
35 Correct 51 ms 8644 KB Output is correct
36 Correct 48 ms 8656 KB Output is correct
37 Correct 210 ms 29340 KB Output is correct
38 Incorrect 81 ms 16144 KB Output isn't correct
39 Incorrect 83 ms 12740 KB Output isn't correct
40 Incorrect 87 ms 16324 KB Output isn't correct
41 Correct 53 ms 11000 KB Output is correct
42 Correct 48 ms 8548 KB Output is correct
43 Correct 48 ms 8516 KB Output is correct
44 Correct 46 ms 8356 KB Output is correct
45 Correct 161 ms 26736 KB Output is correct
46 Incorrect 83 ms 15456 KB Output isn't correct
47 Incorrect 80 ms 16440 KB Output isn't correct
48 Incorrect 83 ms 19552 KB Output isn't correct
49 Correct 58 ms 10880 KB Output is correct
50 Correct 49 ms 8576 KB Output is correct
51 Correct 47 ms 8644 KB Output is correct
52 Correct 48 ms 8656 KB Output is correct
53 Correct 179 ms 26052 KB Output is correct
54 Incorrect 84 ms 15096 KB Output isn't correct