Submission #115415

#TimeUsernameProblemLanguageResultExecution timeMemory
115415shashwatchandraPipes (BOI13_pipes)C++17
74.07 / 100
345 ms38648 KiB
/*input 4 3 -1 1 -3 1 1 2 1 3 1 4 */ #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define double long double #define f first #define s second #define mp make_pair #define pb push_back #define RE(i,n) for (int i = 1; i <= n; i++) #define RED(i,n) for (int i = n; i > 0; i--) #define REPS(i,n) for(int i = 1; (i*i) <= n; i++) #define REP(i,n) for (int i = 0; i < (int)n; i++) #define FOR(i,a,b) for (int i = a; i < b; i++) #define REPD(i,n) for (int i = n-1; i >= 0; i--) #define FORD(i,a,b) for (int i = a; i >= b; i--) #define all(v) v.begin(),v.end() #define pii pair<int,int> #define vi vector<int> #define vvi vector<vi> #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl; #define debug(x) cout << x << endl; #define debug2(x,y) cout << x << " " << y << endl; #define debug3(x,y,z) cout << x << " " << y << " " << z << endl; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int INF = 1e18+1; const int MOD = 1e9+7; const double PI = 3.14159265358979323846264338; int raise(int a,int n,int m = MOD){ if(n == 0)return 1; if(n == 1)return a; int x = 1; x *= raise(a,n/2,m); x %= m; x *= x; x %= m; if(n%2)x*= a; x %= m; return x; } int floor1(int n,int k){ if(n%k == 0 || n >= 0)return n/k; return (n/k)-1; } int ceil1(int n,int k){ return floor1(n+k-1,k); } const int N = 1e5+1; vector<pii> adj[N]; int n,m; int c[N]; int now[N]; int dep[N]; vector<pii> edges; map<pii,int> val; bool works = 0; bool vis[N]; int ans[5*N]; int even = 0; bool odd = 0; void dfs(int u,int p,int ind = -1){ if(vis[u])return; vis[u] = 1; for(auto v:adj[u]){ if(!vis[v.f])dep[v.f] = dep[u]+1; else{ if(v.f == p)continue; if(abs(dep[v.f]-dep[u])%2)odd = 1; else { //cout << u << " " << v << endl; even++; ans[v.s] = 0; } } dfs(v.f,u,v.s); } if(p == -1){ if(!odd)works = (now[u] == c[u]); return; } int diff = c[u]-now[u]; //cout << u 3<< " " << diff << endl; now[p] += diff; ans[ind] = 2*diff; return; } void solve(){ cin >> n >> m; RE(i,n)cin >> c[i]; RE(i,m){ int a,b; cin >> a >> b; adj[a].pb({b,i}); adj[b].pb({a,i}); } dep[1] = 0; dfs(1,-1); if(odd or !works or even > 1){ cout << 0 << endl; return; } RE(i,m){ cout << ans[i] << "\n"; } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //freopen(".in","r",stdin);freopen(".out","w",stdout); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...