oj.uz

답안 #443988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443988 2021-07-12T19:46:30 Z aryan12 Pipes (BOI13_pipes) C++17
74.0741 / 100
 218 ms 29336 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);
		}
	}
	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;
	}
	edgeChange[0] = sum / 2;
	for(int i = 1; i < cycle_edges.size(); i++) {
		edgeChange[i] = change[cycle[i - 1]] - result[cycle[i - 1]] - edgeChange[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:114: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]
  114 |  for(int i = 0; i < cycle.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
pipes.cpp:127: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]
  127 |  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 70 ms 10448 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 3 ms 2764 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 2 ms 2764 KB Output is correct
13 Correct 54 ms 8968 KB Output is correct
14 Correct 65 ms 10084 KB Output is correct
15 Correct 73 ms 10536 KB Output is correct
16 Correct 58 ms 9380 KB Output is correct
17 Correct 70 ms 10500 KB Output is correct
18 Correct 72 ms 10492 KB Output is correct
19 Correct 78 ms 13648 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2764 KB Output is correct
22 Correct 73 ms 10480 KB Output is correct
23 Correct 53 ms 8900 KB Output is correct
24 Correct 70 ms 10564 KB Output is correct
25 Correct 59 ms 9152 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 55 ms 10820 KB Output is correct
4 Correct 49 ms 8572 KB Output is correct
5 Correct 50 ms 8420 KB Output is correct
6 Correct 218 ms 29336 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Incorrect 2 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 2636 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 2764 KB Output is correct
22 Incorrect 2 ms 2764 KB Output isn't correct
23 Incorrect 65 ms 15012 KB Output isn't correct
24 Incorrect 81 ms 16692 KB Output isn't correct
25 Correct 55 ms 10748 KB Output is correct
26 Correct 49 ms 8664 KB Output is correct
27 Correct 48 ms 8488 KB Output is correct
28 Correct 51 ms 8888 KB Output is correct
29 Correct 179 ms 24000 KB Output is correct
30 Incorrect 81 ms 15640 KB Output isn't correct
31 Incorrect 84 ms 19768 KB Output isn't correct
32 Incorrect 76 ms 13296 KB Output isn't correct
33 Correct 58 ms 11180 KB Output is correct
34 Correct 49 ms 8584 KB Output is correct
35 Correct 49 ms 8608 KB Output is correct
36 Correct 49 ms 8580 KB Output is correct
37 Correct 217 ms 29284 KB Output is correct
38 Incorrect 80 ms 16116 KB Output isn't correct
39 Incorrect 74 ms 12632 KB Output isn't correct
40 Incorrect 83 ms 16216 KB Output isn't correct
41 Correct 53 ms 10996 KB Output is correct
42 Correct 49 ms 8448 KB Output is correct
43 Correct 52 ms 8512 KB Output is correct
44 Correct 47 ms 8320 KB Output is correct
45 Correct 178 ms 26740 KB Output is correct
46 Incorrect 84 ms 15416 KB Output isn't correct
47 Incorrect 81 ms 16380 KB Output isn't correct
48 Incorrect 84 ms 19512 KB Output isn't correct
49 Correct 62 ms 10932 KB Output is correct
50 Correct 48 ms 8620 KB Output is correct
51 Correct 48 ms 8640 KB Output is correct
52 Correct 48 ms 8464 KB Output is correct
53 Correct 178 ms 26072 KB Output is correct
54 Incorrect 80 ms 14988 KB Output isn't correct