Submission #1186732

#TimeUsernameProblemLanguageResultExecution timeMemory
1186732sasdePipes (BOI13_pipes)C++20
74.07 / 100
76 ms68168 KiB
#include<bits/stdc++.h> #define task "strdel" #define int long long #define ii pair<int,int> #define iii pair<int,ii> #define iv pair<ii,ii> #define se second #define fi first #define ffi fi.fi #define sfi se.fi #define sse se.se #define fse fi.se #define lt(i, c, d) for(int i = c; i <= d; ++i) #define fl(i, c, d) for(int i = d; i >= c; --i) #define pb push_back #define emb emplace_back #define emf emplace_front #define em emplace using namespace std; const int N=1e6+5,lg=20,mod=1e9+7; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int u,int v){ return u+rd()%(v-u+1); } int c[N],m,n,sum,gg,ans[N],d[N]; set<ii>a[N]; bool k[N],k1[N]; void dfs(int u,int i){ k[u]=true; sum+=c[u]*i; for(ii v:a[u]){ if(!k[v.fi]){ gg=v.se; dfs(v.fi,i*-1); } } } ii b[N]; void solve(){ cin >> n >> m; if(m>n){ cout <<0;return; } for(int i=1;i<=n;++i)cin >> c[i],d[i]=c[i]; for(int i=1;i<=m;++i){ int u,v; cin >> u >> v; a[u].insert({v,i}); b[i]={u,v}; a[v].insert({u,i}); } int sl=0; queue<int>p; for(int i=1;i<=n;++i){ if(a[i].size()==1){ p.push(i); k[i]=true; // cout <<i<<" "; } } int cnt=0; while(!p.empty()){ int u=p.front(); p.pop();++cnt; if(a[u].size()){ ii v=*a[u].begin(); a[u].erase(v); a[v.fi].erase({u,v.se}); ans[v.se]+=c[u]; c[v.fi]-=c[u]; if(a[v.fi].size()==1&&!k[v.fi]){ k[v.fi]=true; p.push(v.fi); } } } if(cnt!=n&&(n-cnt)%2==0){ cout <<0;return; } int st=0; for(int i=1;i<=n;++i){ if(!k[i])st=i; } dfs(st,1); ans[gg]=sum/2; int u=b[gg].fi; int v=b[gg].se; k1[gg]=true; c[u]-=ans[gg]; c[v]-=ans[gg]; p.push(u); p.push(v); while(!p.empty()){ int u=p.front(); p.pop(); for(ii v:a[u]){ if(!k1[v.se]){ ans[v.se]=c[u]; c[v.fi]-=c[u]; // cout <<v.se<<" "; k1[v.se]=true; p.push(v.fi); } } } for(int i=1;i<=m;++i){ d[b[i].fi]-=ans[i]; d[b[i].se]-=ans[i]; } for(int i=1;i<=n;++i){ if(d[i]!=0){ cout <<0;return; } } for(int i=1;i<=m;++i)cout <<2*ans[i]<<'\n'; } main() { srand(time(0)); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int t=1; // cin >> t; while(t--){ solve(); // cout<<'\n'; } }

Compilation message (stderr)

pipes.cpp:122:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  122 | main()
      | ^~~~
pipes.cpp: In function 'int main()':
pipes.cpp:129:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:130:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...