Submission #555932

#	Time	Username	Problem	Language	Result	Execution time	Memory
555932		new_acc	Pipes (BOI13_pipes)	C++14	74.07 / 100	178 ms	38012 KiB

pipes

#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]]]=(-(ans[val[c[i-1]]]>>1)-t[c[i-1]])<<1;
    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]]]=(-(ans[val[c[i-1]]]>>1)-t[c[i-1]])<<1;
      |                 ~^~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 44.074074074074076 / 70