oj.uz

Submission #483561

# Submission time Handle Problem Language Result Execution time Memory
483561 2021-10-30T18:06:19 Z robell Pipes (BOI13_pipes) C++14
74.0741 / 100
 159 ms 23628 KB 
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
#define pb push_back
#define eb emplace_back
#define countbits __builtin_popcount
#define beg0 __builtin_clz
#define terminal0 __builtin_ctz
#define f first
#define s second
int mod=1e9+7;
void setIO(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
void setIO(string f){
	freopen((f+".in").c_str(),"r",stdin);
	freopen((f+".out").c_str(),"w",stdout);
	setIO();
}
ll N, M,pump[(int)5e5],c[(int)1e5];
vector<pair<int,int>> l[(int)1e5];
bool cyc = false,v[(int)1e5];
void dfs2(int ind, int p){
	if (cyc) return;
	v[ind]=true;
	for (pair<int,int> j:l[ind]){
		if (cyc) break;
		if (j.first==p) continue;
		if (v[j.first]){cyc=true;return;}
		else{
			dfs2(j.first,ind);
		}
	}
}
ll dfs(int ind, int p){
	v[ind]=true;
	ll val = c[ind];
	for (pair<int,int> j:l[ind]){
		if (j.first==p) continue;
		pump[j.second]=dfs(j.first,ind);
		val-=pump[j.second];
	}
	return val;
}
int main(){
	setIO(); cin >> N >> M;
	for (int i=0;i<N;i++) cin >> c[i];
	for (int i=0;i<M;i++){
		int u,v; cin >> u >> v;
		l[--u].pb({--v,i});
		l[v].pb({u,i});
	}
	for (int i=0;i<N;i++){
		if (!v[i]) dfs2(i,i);
	}
	if (cyc){cout << "0\n";return 0;}
	memset(v,0,sizeof(v));
	for (int i=0;i<N;i++){
		if (!v[i]) dfs(i,i);
	}
	for (int i=0;i<M;i++){
		cout << 2*pump[i] << "\n";
	}
}

Compilation message

pipes.cpp: In function 'void setIO(std::string)':
pipes.cpp:21:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  freopen((f+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((f+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 1 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 52 ms 9984 KB Output is correct
5 Correct 1 ms 2764 KB Output is correct
6 Correct 1 ms 2764 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 1 ms 2764 KB Output is correct
9 Correct 2 ms 2812 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 40 ms 8440 KB Output is correct
14 Correct 48 ms 9540 KB Output is correct
15 Correct 51 ms 10020 KB Output is correct
16 Correct 42 ms 8940 KB Output is correct
17 Correct 57 ms 10040 KB Output is correct
18 Correct 55 ms 10032 KB Output is correct
19 Correct 61 ms 12468 KB Output is correct
20 Correct 2 ms 2764 KB Output is correct
21 Correct 2 ms 2764 KB Output is correct
22 Correct 54 ms 9996 KB Output is correct
23 Correct 40 ms 8464 KB Output is correct
24 Correct 52 ms 10032 KB Output is correct
25 Correct 46 ms 8908 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Correct 39 ms 10280 KB Output is correct
4 Correct 42 ms 11880 KB Output is correct
5 Correct 34 ms 8552 KB Output is correct
6 Correct 151 ms 23552 KB Output is correct
7 Incorrect 1 ms 2636 KB Output isn't correct
8 Incorrect 1 ms 2636 KB Output isn't correct
9 Correct 2 ms 2676 KB Output is correct
10 Correct 1 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 2636 KB Output isn't correct
17 Correct 2 ms 2636 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 2 ms 2764 KB Output is correct
22 Incorrect 2 ms 2636 KB Output isn't correct
23 Incorrect 33 ms 9800 KB Output isn't correct
24 Incorrect 42 ms 11000 KB Output isn't correct
25 Correct 38 ms 10288 KB Output is correct
26 Correct 41 ms 11464 KB Output is correct
27 Correct 38 ms 9668 KB Output is correct
28 Correct 36 ms 8648 KB Output is correct
29 Correct 127 ms 19720 KB Output is correct
30 Incorrect 42 ms 12148 KB Output isn't correct
31 Incorrect 42 ms 12372 KB Output isn't correct
32 Incorrect 40 ms 9416 KB Output isn't correct
33 Correct 41 ms 11000 KB Output is correct
34 Correct 41 ms 10948 KB Output is correct
35 Correct 42 ms 11856 KB Output is correct
36 Correct 35 ms 8576 KB Output is correct
37 Correct 159 ms 23628 KB Output is correct
38 Incorrect 39 ms 10444 KB Output isn't correct
39 Incorrect 38 ms 9172 KB Output isn't correct
40 Incorrect 40 ms 10820 KB Output isn't correct
41 Correct 46 ms 12344 KB Output is correct
42 Correct 40 ms 10088 KB Output is correct
43 Correct 43 ms 12112 KB Output is correct
44 Correct 34 ms 8492 KB Output is correct
45 Correct 114 ms 20800 KB Output is correct
46 Incorrect 45 ms 12712 KB Output isn't correct
47 Incorrect 40 ms 10832 KB Output isn't correct
48 Incorrect 42 ms 12224 KB Output isn't correct
49 Correct 36 ms 9088 KB Output is correct
50 Correct 42 ms 11092 KB Output is correct
51 Correct 38 ms 9924 KB Output is correct
52 Correct 36 ms 8892 KB Output is correct
53 Correct 120 ms 20684 KB Output is correct
54 Incorrect 48 ms 11428 KB Output isn't correct