제출 #285734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285734		kostia244	Pipes (BOI13_pipes)	C++17	100 / 100	263 ms	39684 KiB

pipes

    #pragma GCC optimize("Ofast")
    #include<bits/stdc++.h>
    #define all(v) (v).begin(),(v).end()
    using ll = long long;
    using namespace std;
    const int maxn = 1<<19;
    int n, m;
    vector<array<ll, 2>> g[maxn];
    ll val[maxn];
    ll vis[maxn], C[maxn], h[maxn], L = -1, R, ID= -69, bb;
    ll s = 0;
    void dfs(int v, int p) {
    	ll cur = C[v];
    	vis[v] = 1;
    	if(h[v]&1) s -= C[v];
    	else s += C[v];
    	for(auto &[i, id] : g[v]) if(i != p) {
    		if(!vis[i]) {
    			h[i] = h[v]+1;
    			dfs(i, v);
    		} else if(h[i] < h[v]) {
    			if(L != -1 || (h[i]&1) != (h[v]&1)) {cout << "0\n", exit(0);}
    			L = i, R = v, ID = id, bb = h[v]&1;
    		}
    	}
    }
    ll recover(int v, int p) {
    	ll cur = C[v];
    	for(auto [i, id] : g[v]) if(i != p && id != ID) {
    		ll t = recover(i, v);
    		val[id] = t;
    		cur += t;
    	}
    	return -cur;
    }
    signed main() {
    	cin.tie(0)->sync_with_stdio(0);
    	cin >> n >> m;
    	for(int i = 1; i <= n; i++) cin >> C[i];
    	for(int f, t, i = 0; i < m; i++) {
    		cin >> f >> t;
    		g[f].push_back({t, i});
    		g[t].push_back({f, i});
    	}
    	dfs(1, 1);
    	if(L != -1) {
    		//cout << ID << ":\n";
    		if(bb) s *= -1;
    		C[L] -= s/2;
    		C[R] -= s/2;
    		val[ID] = (-s)/2;
    	}
    	recover(1, 1);
    	for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
    }
    //?VK
    //??V
    //K?

컴파일 시 표준 에러 (stderr) 메시지

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:13:9: warning: unused variable 'cur' [-Wunused-variable]
   13 |      ll cur = C[v];
      |         ^~~
pipes.cpp: In function 'int main()':
pipes.cpp:54:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |      for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
      |      ^~~
pipes.cpp:54:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   54 |      for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
      |                                                              ^~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70