Submission #1186742

#TimeUsernameProblemLanguageResultExecution timeMemory
1186742sasdePipes (BOI13_pipes)C++20
74.07 / 100
81 ms66484 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],s[N]; set<ii>a[N]; bool k[N]; vector<int>cir,ed; 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; auto v=*a[u].begin(); c[v.fi]-=c[u]; ans[v.se]+=c[u]; a[v.fi].erase({u,v.se}); if(a[v.fi].size()<2&&!k[v.fi]){ p.push(v.fi); k[v.fi]=1; } } if((n-cnt)%2==0){ cout <<0;return; } int st=0; for(int i=1;i<=n;++i){ if(!k[i])st=i; } int u=st; while(cir.empty()||u!=st){ ii v=(cir.empty()||(*a[u].begin()).fi!=cir.back()?*(a[u].begin()):*(a[u].rbegin())); cir.emb(u); ed.emb(v.se); u=v.fi; } for(int i=cir.size()-1;i>=0;--i){ s[i]=c[cir[i]]-s[i+1]; } int pr=0; for(int i=0;i<cir.size();++i){ pr=c[cir[i]]-pr; ans[ed[i]]=(s[i]+pr)/2; } 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:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main()
      | ^~~~
pipes.cpp: In function 'int main()':
pipes.cpp:100:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:101:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...