oj.uz

Submission #230453

# Submission time Handle Problem Language Result Execution time Memory
230453 2020-05-10T07:15:40 Z BamiTorabi Pipes (BOI13_pipes) C++14
37.5926 / 100
 1000 ms 62680 KB 
//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e5 + 5;
const int maxM = 5e5 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

bool mark[maxN];
int c[maxN];
set <int> G[maxN];
vector <int> vec;
vector <pii> E;
map <pii, int> mp;
queue <int> Q;

pii sorted(int u, int v){
	return {min(u, v), max(u, v)};
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++){
		scanf("%d", c + i);
		c[i] *= 2;
	}
	for (int i = 0; i < m; i++){
		int u, v; scanf("%d%d", &u, &v);
		tie(u, v) = sorted(u, v);
		G[u].insert(v);
		G[v].insert(u);
		E.push_back({u, v});
	}
	if (m > n)
		return printf("0\n"), 0;
	for (int i = 1; i <= n; i++)
		if ((int)G[i].size() == 1)
			Q.push(i);
	while (!Q.empty()){
		int v = Q.front();
		Q.pop();
		if ((int)G[v].size() != 2)
			continue;
		int u = *G[v].begin();
		G[v].clear();
		mp[sorted(u, v)] = c[v];
		c[u] -= c[v];
		G[u].erase(G[u].lower_bound(v));
		if ((int)G[u].size() == 1)
			Q.push(u);
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += ((int)G[i].size() == 2);
	if (cnt > 0 && cnt % 2 == 0)
		return printf("0\n"), 0;
	if (cnt)
		for (int i = 1; i <= n; i++)
			if ((int)G[i].size() == 2){
				vec.push_back(i);
				int u = *(G[i].begin());
				G[i].erase(G[i].begin());
				int x = *(G[i].begin());
				G[x].erase(G[x].lower_bound(i));
				ll ans = c[i];
				while (x != i){
					vec.push_back(x);
					ans = c[x] - ans;
					int y = *(G[x].begin());
					G[x].erase(G[x].begin());
					if (y != i)	
						G[y].erase(G[y].lower_bound(x));
					x = y;
				}
				c[u] -= ans / 2;
				c[i] -= ans / 2;
				mp[sorted(i, u)] = ans / 2;
				break;
			}
	for (int i = 1; i < (int)vec.size(); i++){
		mp[sorted(vec[i - 1], vec[i])] = c[vec[i - 1]];
		c[vec[i]] -= c[vec[i - 1]];
	}
	for (pii e : E)
		printf("%d\n", mp[e]);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", c + i);
   ~~~~~^~~~~~~~~~~~~
pipes.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4992 KB Output isn't correct
2 Execution timed out 1094 ms 4992 KB Time limit exceeded
3 Incorrect 8 ms 5248 KB Output isn't correct
4 Execution timed out 1091 ms 17388 KB Time limit exceeded
5 Execution timed out 1085 ms 4992 KB Time limit exceeded
6 Incorrect 7 ms 5120 KB Output isn't correct
7 Execution timed out 1092 ms 4992 KB Time limit exceeded
8 Execution timed out 1096 ms 4992 KB Time limit exceeded
9 Execution timed out 1091 ms 5120 KB Time limit exceeded
10 Incorrect 8 ms 5248 KB Output isn't correct
11 Execution timed out 1086 ms 5120 KB Time limit exceeded
12 Execution timed out 1094 ms 5120 KB Time limit exceeded
13 Incorrect 68 ms 14828 KB Output isn't correct
14 Execution timed out 1095 ms 16620 KB Time limit exceeded
15 Execution timed out 1095 ms 17364 KB Time limit exceeded
16 Execution timed out 1093 ms 15468 KB Time limit exceeded
17 Execution timed out 1092 ms 17372 KB Time limit exceeded
18 Incorrect 89 ms 17388 KB Output isn't correct
19 Incorrect 86 ms 17260 KB Output isn't correct
20 Incorrect 7 ms 4992 KB Output isn't correct
21 Incorrect 9 ms 5120 KB Output isn't correct
22 Incorrect 93 ms 17388 KB Output isn't correct
23 Incorrect 69 ms 14956 KB Output isn't correct
24 Execution timed out 1082 ms 17428 KB Time limit exceeded
25 Incorrect 85 ms 15340 KB Output isn't correct

Subtask #2
37.5925925926 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 5120 KB Time limit exceeded
2 Incorrect 8 ms 5120 KB Output isn't correct
3 Execution timed out 1093 ms 16624 KB Time limit exceeded
4 Correct 86 ms 17132 KB Output is correct
5 Correct 83 ms 16748 KB Output is correct
6 Correct 528 ms 62556 KB Output is correct
7 Execution timed out 1091 ms 4992 KB Time limit exceeded
8 Incorrect 7 ms 5120 KB Output isn't correct
9 Execution timed out 1091 ms 4992 KB Time limit exceeded
10 Correct 7 ms 5120 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 7 ms 5120 KB Output is correct
14 Incorrect 7 ms 5120 KB Output isn't correct
15 Incorrect 8 ms 5120 KB Output isn't correct
16 Incorrect 8 ms 5120 KB Output isn't correct
17 Execution timed out 1097 ms 5120 KB Time limit exceeded
18 Correct 8 ms 5120 KB Output is correct
19 Correct 8 ms 5120 KB Output is correct
20 Correct 8 ms 5248 KB Output is correct
21 Correct 9 ms 5376 KB Output is correct
22 Execution timed out 1088 ms 5120 KB Time limit exceeded
23 Execution timed out 1087 ms 15084 KB Time limit exceeded
24 Execution timed out 1096 ms 17640 KB Time limit exceeded
25 Execution timed out 1094 ms 16620 KB Time limit exceeded
26 Correct 85 ms 17260 KB Output is correct
27 Correct 81 ms 17132 KB Output is correct
28 Correct 91 ms 17900 KB Output is correct
29 Correct 388 ms 51292 KB Output is correct
30 Incorrect 84 ms 17004 KB Output isn't correct
31 Incorrect 83 ms 17260 KB Output isn't correct
32 Execution timed out 1091 ms 17384 KB Time limit exceeded
33 Correct 89 ms 17260 KB Output is correct
34 Correct 84 ms 17256 KB Output is correct
35 Correct 86 ms 17132 KB Output is correct
36 Correct 83 ms 17388 KB Output is correct
37 Correct 497 ms 62680 KB Output is correct
38 Incorrect 83 ms 17256 KB Output isn't correct
39 Execution timed out 1087 ms 17260 KB Time limit exceeded
40 Execution timed out 1092 ms 17644 KB Time limit exceeded
41 Execution timed out 1094 ms 17260 KB Time limit exceeded
42 Correct 89 ms 17176 KB Output is correct
43 Correct 85 ms 17260 KB Output is correct
44 Correct 82 ms 16876 KB Output is correct
45 Correct 480 ms 55644 KB Output is correct
46 Execution timed out 1080 ms 17260 KB Time limit exceeded
47 Execution timed out 1090 ms 17516 KB Time limit exceeded
48 Incorrect 100 ms 17260 KB Output isn't correct
49 Correct 77 ms 16616 KB Output is correct
50 Correct 82 ms 17132 KB Output is correct
51 Correct 94 ms 17260 KB Output is correct
52 Correct 78 ms 17004 KB Output is correct
53 Correct 482 ms 56796 KB Output is correct
54 Incorrect 85 ms 17128 KB Output isn't correct