Submission #555934

#TimeUsernameProblemLanguageResultExecution timeMemory
555934new_accPipes (BOI13_pipes)C++14
100 / 100
154 ms38092 KiB
#include<bits/stdc++.h> #define fi first #define se second #define pitem item* using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vl; const int N=1e6+10; const int SS=1<<19; const int INFi=2e9; const ll INFl=1e13; const ll mod2=998244353; const ll mod=1e9+7; const ll mod3=1000696969; const ll p=70032301; const ull p2=913; const int L=20; int t[N],ans[N],val[N]; vector<pair<int,int> >graf[N]; vi __curr; bool vis[N]; void wa(){ cout<<0<<"\n"; exit(0); } ll dfs(int v){ if(vis[v]) return 0; vis[v]=1; ll sum=0; for(auto u:graf[v]){ ll curr=dfs(u.fi); sum+=curr,ans[u.se]=(curr<<1); } return (ll)t[v]-sum; } void dfs2(int v,vi *c,int o,int num){ if(c->size()) return; val[v]=num; if(vis[v]){ c->push_back(v); while(__curr[__curr.size()-1]!=v) c->push_back(__curr[__curr.size()-1]),__curr.pop_back(); return; } vis[v]=1; __curr.push_back(v); for(auto u:graf[v]) if(o!=u.fi) dfs2(u.fi,c,v,u.se); __curr.pop_back(); } void solve(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>t[i]; for(int a,b,i=1;i<=m;i++){ cin>>a>>b; graf[a].push_back({b,i}),graf[b].push_back({a,i}); } if(m>n) wa(); if(m==n-1){ if(dfs(1)) wa(); for(int i=1;i<=m;i++) cout<<ans[i]<<"\n"; return; } vi c; dfs2(1,&c,1,0); if(!(c.size()&1)) wa(); reverse(c.begin(),c.end()); for(int i=1;i<=n;i++) vis[i]=0; for(int i=0;i<c.size();i++){ int pop=(i==0?c[c.size()-1]:c[i-1]),nxt=(i==c.size()-1?c[0]:c[i+1]); vis[pop]=1,vis[nxt]=1; t[c[i]]=dfs(c[i]); vis[pop]=0,vis[nxt]=0; } ll sum1=0,sum2=0; for(int i=1;i<c.size();i+=2) sum1+=(ll)t[c[i]]; sum1<<=1LL; for(int i=0;i<c.size();i++) sum2+=(ll)t[c[i]]; ans[val[c[0]]]=sum2-sum1; if(ans[val[c[0]]]&1LL) wa(); for(int i=1;i<c.size();i++) ans[val[c[i]]]=(t[c[i-1]]-(ans[val[c[i-1]]]>>1))<<1LL; if(t[c[c.size()-1]]!=((ans[val[c[c.size()-1]]]+ans[val[c[0]]])>>1)) wa(); for(int i=1;i<=m;i++) cout<<ans[i]<<"\n"; } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); int tt=1; while(tt--) solve(); }

Compilation message (stderr)

pipes.cpp: In function 'void solve()':
pipes.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<c.size();i++){
      |                 ~^~~~~~~~~
pipes.cpp:71:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         int pop=(i==0?c[c.size()-1]:c[i-1]),nxt=(i==c.size()-1?c[0]:c[i+1]);
      |                                                  ~^~~~~~~~~~~~
pipes.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=1;i<c.size();i+=2) sum1+=(ll)t[c[i]];
      |                 ~^~~~~~~~~
pipes.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<c.size();i++) sum2+=(ll)t[c[i]];
      |                 ~^~~~~~~~~
pipes.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=1;i<c.size();i++) ans[val[c[i]]]=(t[c[i-1]]-(ans[val[c[i-1]]]>>1))<<1LL;
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...