Submission #885549

#TimeUsernameProblemLanguageResultExecution timeMemory
8855498pete8Pipes (BOI13_pipes)C++17
100 / 100
281 ms42816 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<limits.h> #include <cassert> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") using namespace std; #define int long long const int mod=1e9+7,mxn=5e5+5,lg=30,inf=1e18,minf=-1e18; int ans[mxn+10],val[mxn+10],up[mxn+10],curval[mxn+10]; vector<pii>adj[mxn+10]; bitset<mxn+10>vis; bool yes=false; void solve(int cur,int p){ if(vis[cur])return void(yes=true); vis[cur]=true; bool leaf=true; for(auto i:adj[cur])if(i.f!=p)leaf=false; if(leaf){ ans[up[cur]]+=val[cur]; curval[p]+=val[cur]; return; } for(auto i:adj[cur]){ if(i.f==p)continue; up[i.f]=i.s; solve(i.f,cur); } if(cur==1)return; ans[up[cur]]+=(val[cur]-curval[cur]); curval[p]+=(val[cur]-curval[cur]); } vector<ppii>path; int deg[mxn+10],sum,cnt=0; int tin[mxn+10]; int start=1,t=0; void solve2(int cur,int p){ if(vis[cur])return; cnt++; tin[cur]=t++; if(cnt%2)sum+=(val[cur]-curval[cur]); else sum-=(val[cur]-curval[cur]); vis[cur]=true; for(auto i:adj[cur]){ if(i.f==start&&i.f!=p){ path.pb({i.s,{i.f,cur}}); return; } if(i.f!=p&&!vis[i.f]){ path.pb({i.s,{i.f,cur}}); solve2(i.f,cur); } } } int32_t main(){ int n,m;cin>>n>>m; for(int i=1;i<=n;i++)cin>>val[i]; for(int i=0;i<m;i++){ int a,b;cin>>a>>b; adj[a].pb({b,i}); adj[b].pb({a,i}); } if(m>n){ cout<<0; return 0; } if(m==n-1){ solve(1,-1); for(int i=0;i<m;i++)cout<<2*ans[i]<<'\n'; return 0; } queue<int>st; for(int i=1;i<=n;i++){ if(adj[i].size()==1)st.push(i); deg[i]=adj[i].size(); } cnt=0; int add; while(!st.empty()){ vis[st.front()]=true; for(auto i:adj[st.front()]){ if(vis[i.f])continue; deg[i.f]--; add=val[st.front()]-curval[st.front()]; ans[i.s]+=add; curval[i.f]+=add; curval[st.front()]+=add; if(deg[i.f]<=1){ st.push(i.f); vis[i.f]=true; } } st.pop(); cnt++; } for(int i=1;i<=n;i++)if(!vis[i])start=i; for(int i=1;i<=n;i++)if(!vis[i]&&curval[i]!=0)start=i; if((n-cnt)%2==0){ cout<<0; return 0; } cnt=0; solve2(start,-1); sum/=2; reverse(all(path)); for(int i=0;i<path.size();i++){ if(i==0)add=sum; else add=val[path[i].s.f]-curval[path[i].s.f]; ans[path[i].f]+=add; curval[path[i].s.f]+=add; curval[path[i].s.s]+=add; } /* */ for(int i=0;i<m;i++)cout<<2*ans[i]<<'\n'; }

Compilation message (stderr)

pipes.cpp: In function 'int32_t main()':
pipes.cpp:132:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i=0;i<path.size();i++){
      |                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...