oj.uz

Submission #483572

# Submission time Handle Problem Language Result Execution time Memory
483572 2021-10-30T20:09:25 Z robell Pipes (BOI13_pipes) C++14
65 / 100
 161 ms 17208 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],change[(int)1e5];
int start = 0;
vector<pair<int,int>> l[(int)1e5];
vector<int> fcyc;
bool cyc = false,v[(int)1e5],oncyc[(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;
}
void findcyc(int ind){
	v[ind]=true;
	fcyc.pb(ind);
	for (pair<int,int> e:l[ind]){
		if (!v[e.first]){
			findcyc(e.first);
		}else if (!oncyc[e.first]&& fcyc.size()>=2 && fcyc[fcyc.size()-2]!=ind){
			for (int i=fcyc.size()-1;fcyc[i]!=e.f;i--){
				oncyc[fcyc[i]]=true;
			}
			oncyc[e.f]=true;
		}
	}
	fcyc.pop_back();
}
void prefix(int x,int p,int p0){
	for(auto v:l[x]){
		if(!oncyc[v.f] || v.f==p || v.f==p0)
			continue;
		change[v.f]=c[v.f]-change[x];
		prefix(v.f,x,p0);
		return;
	}
	start=change[x];
	return;
}
void solve_trees(int x,int p){
	for(auto v:l[x]){
		if(oncyc[v.f] || v.f==p)
			continue;
		solve_trees(v.f,x);
		pump[v.s]=2*c[v.f];
		c[x]-=c[v.f];
	}
	return;
}
void solvec(int x,int p,int p0,bool sgn_x){
	for(auto v:l[x]){
		if(!oncyc[v.f] || v.f==p)continue;
		if(v.f==p0){pump[v.s]=start;return;}
		if(sgn_x) pump[v.s]=-start+2*change[x];
		else pump[v.s]=start+2*change[x];
		solvec(v.f,x,p0,!sgn_x);
		return;
	}
	return;
}
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});
	}
	if (M>N){cout << "0\n";return 0;}
	if (M<N){
		for (int i=0;i<N;i++){
			if (!v[i]) dfs2(i,i);
		}
		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";
		}
	}else{
		findcyc(0);
		int countc=0,start=0;
		for (int i=0;i<N;i++){
			if (oncyc[i]){
				solve_trees(i,0);
				countc++;
				start=i;
			}
		}
		if (countc%2==0){
			cout << "0\n";
		}
		change[start]=c[start];
		prefix(start,0,start);
		solvec(start,0,start,1);
		for (int i=0;i<M;i++){
			cout << pump[i] << " ";
		}
	}
}

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 1 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 50 ms 8448 KB Output is correct
5 Correct 1 ms 2764 KB Output is correct
6 Correct 1 ms 2764 KB Output is correct
7 Correct 1 ms 2764 KB Output is correct
8 Correct 2 ms 2764 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 2764 KB Output is correct
12 Correct 2 ms 2820 KB Output is correct
13 Correct 38 ms 7232 KB Output is correct
14 Correct 47 ms 8176 KB Output is correct
15 Correct 59 ms 8496 KB Output is correct
16 Correct 44 ms 7620 KB Output is correct
17 Correct 50 ms 8388 KB Output is correct
18 Correct 54 ms 8388 KB Output is correct
19 Correct 57 ms 10980 KB Output is correct
20 Correct 2 ms 2764 KB Output is correct
21 Correct 2 ms 2764 KB Output is correct
22 Correct 64 ms 8528 KB Output is correct
23 Correct 38 ms 7236 KB Output is correct
24 Correct 53 ms 8448 KB Output is correct
25 Correct 41 ms 7492 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5180 KB Execution killed with signal 11
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Incorrect 58 ms 10856 KB Output isn't correct
4 Correct 35 ms 6684 KB Output is correct
5 Correct 33 ms 6872 KB Output is correct
6 Correct 156 ms 17204 KB Output is correct
7 Runtime error 5 ms 5252 KB Execution killed with signal 11
8 Incorrect 1 ms 2636 KB Output isn't correct
9 Incorrect 1 ms 2636 KB Output isn't 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 1 ms 2636 KB Output is correct
14 Incorrect 1 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 Incorrect 2 ms 2764 KB Output isn't correct
18 Correct 1 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 Runtime error 5 ms 5384 KB Execution killed with signal 11
23 Incorrect 44 ms 11168 KB Output isn't correct
24 Incorrect 59 ms 12452 KB Output isn't correct
25 Incorrect 61 ms 10948 KB Output isn't correct
26 Correct 35 ms 6724 KB Output is correct
27 Correct 34 ms 6516 KB Output is correct
28 Correct 34 ms 7016 KB Output is correct
29 Correct 128 ms 14600 KB Output is correct
30 Incorrect 85 ms 13828 KB Output isn't correct
31 Incorrect 53 ms 14480 KB Output isn't correct
32 Incorrect 49 ms 9540 KB Output isn't correct
33 Incorrect 70 ms 12772 KB Output isn't correct
34 Correct 33 ms 6572 KB Output is correct
35 Correct 37 ms 6716 KB Output is correct
36 Correct 51 ms 6964 KB Output is correct
37 Correct 161 ms 17208 KB Output is correct
38 Incorrect 59 ms 13700 KB Output isn't correct
39 Incorrect 60 ms 9028 KB Output isn't correct
40 Incorrect 57 ms 11452 KB Output isn't correct
41 Incorrect 56 ms 13708 KB Output isn't correct
42 Correct 39 ms 6476 KB Output is correct
43 Correct 42 ms 6532 KB Output is correct
44 Correct 34 ms 6852 KB Output is correct
45 Correct 138 ms 15372 KB Output is correct
46 Incorrect 55 ms 14392 KB Output isn't correct
47 Incorrect 51 ms 11448 KB Output isn't correct
48 Incorrect 54 ms 14236 KB Output isn't correct
49 Incorrect 52 ms 9136 KB Output isn't correct
50 Correct 33 ms 6684 KB Output is correct
51 Correct 36 ms 6860 KB Output is correct
52 Correct 33 ms 6656 KB Output is correct
53 Correct 117 ms 15236 KB Output is correct
54 Incorrect 54 ms 12492 KB Output isn't correct