Submission #659225

#TimeUsernameProblemLanguageResultExecution timeMemory
659225Soul234Pipes (BOI13_pipes)C++14
87.04 / 100
165 ms35384 KiB
#include<bits/stdc++.h> using namespace std; void DBG() { cerr << "]\n"; } template<class H, class... T> void DBG(H h, T... t) { cerr << h; if(sizeof...(t)) cerr << ", "; DBG(t...); } #ifdef LOCAL #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif // LOCAL #define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--) #define R0F(i,a) ROF(i,0,a) #define each(e,a) for(auto &e : (a)) #define sz(v) (int)(v).size() #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pb push_back #define tcT template<class T #define nl "\n" #define fi first #define se second #define int long long using ll = long long; using vi = vector<int>; using pi = pair<int,int>; using str = string; using db = long double; tcT> using V = vector<T>; tcT> using pqg = priority_queue<T,vector<T>,greater<T>>; void setIO(string NAME = "") { cin.tie(0)->sync_with_stdio(0); if(sz(NAME)) { freopen((NAME + ".inp").c_str(),"r",stdin); freopen((NAME + ".out").c_str(),"w",stdout); } } tcT> bool ckmin(T&a, const T&b) { return b < a ? a=b,1 : 0; } tcT> bool ckmax(T&a, const T&b) { return b > a ? a=b,1 : 0; } const int MOD = 1e9 + 7; const ll INF = 1e18; const int MX = 5e5+5; int N, M; vi adj[MX]; int tin[MX], tt; int deg[MX], val[MX]; pi eds[MX]; bool used[MX], vis[MX]; int ans[MX]; void dfs(int u, int p) { tin[u] = ++tt; each(id, adj[u]) if(!used[id]) { used[id] = true; int v = eds[id].fi ^ eds[id].se ^ u; if(tin[v]) { if((tin[v]-tin[u])&1) { cout << "0\n"; exit(0); } } else { dfs(v, u); } } } vi lst, lstid; ll sum = 0; int src; void dfsList(int u, int p) { lst.pb(u); vis[u] = 1; sum += val[u]; each(id, adj[u]) { int v = u ^ eds[id].fi ^ eds[id].se; if(deg[v] == 2 && v != p) { if(!vis[v] || v == src) lstid.pb(id); } if(!vis[v] && deg[v] == 2) { dfsList(v, u); return; } } } void solve() { cin >> N >> M; FOR(i,1,N+1) cin >> val[i]; F0R(i, M) { int u, v; cin >> u >> v; adj[u].pb(i); adj[v].pb(i); eds[i] = {u, v}; deg[u]++; deg[v]++; } if(M > N) { cout << "0\n"; return; } dfs(1, -1); queue<int> q; FOR(i,1,N+1) if(deg[i] == 1) { q.push(i); } memset(used, false, sizeof used); while(sz(q)) { int u = q.front(); q.pop(); each(id, adj[u]) if(!used[id]) { used[id] = true; int v = eds[id].fi ^ eds[id].se ^ u; val[v] -= val[u]; ans[id] = val[u]; if(--deg[v] == 1) { q.push(v); } } } FOR(i,1,N+1) if(deg[i] == 2) { src = i; dfsList(i, -1); break; } sum /= 2; if(!lstid.empty()) { for(int i = 2; i<sz(lst); i += 2) { sum -= val[lst[i]]; } // each(id, lstid) dbg(id); // dbg(sum); ans[lstid[0]] = sum; for(int i = 1; i<sz(lstid); i++) { ans[lstid[i]] = val[lst[i]] - ans[lstid[i-1]]; } } F0R(i, M) { cout << 2*ans[i] << nl; } } signed main() { setIO(); int t=1; //cin>>t; while(t-->0) { solve(); } return 0; }

Compilation message (stderr)

pipes.cpp: In function 'void setIO(std::string)':
pipes.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...