oj.uz

Submission #555932

# Submission time Handle Problem Language Result Execution time Memory
555932 2022-05-01T20:29:11 Z new_acc Pipes (BOI13_pipes) C++14
74.0741 / 100
 178 ms 38012 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23772 KB Output is correct
2 Correct 13 ms 23800 KB Output is correct
3 Correct 13 ms 23828 KB Output is correct
4 Correct 62 ms 28852 KB Output is correct
5 Correct 13 ms 23832 KB Output is correct
6 Correct 12 ms 23740 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23788 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 14 ms 23808 KB Output is correct
11 Correct 15 ms 23832 KB Output is correct
12 Correct 13 ms 23904 KB Output is correct
13 Correct 49 ms 27832 KB Output is correct
14 Correct 58 ms 28472 KB Output is correct
15 Correct 69 ms 28756 KB Output is correct
16 Correct 52 ms 27996 KB Output is correct
17 Correct 61 ms 28864 KB Output is correct
18 Correct 61 ms 28876 KB Output is correct
19 Correct 66 ms 31396 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23788 KB Output is correct
22 Correct 63 ms 28876 KB Output is correct
23 Correct 49 ms 27788 KB Output is correct
24 Correct 64 ms 28816 KB Output is correct
25 Correct 53 ms 28024 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23816 KB Output isn't correct
2 Incorrect 12 ms 23892 KB Output isn't correct
3 Correct 57 ms 31208 KB Output is correct
4 Correct 45 ms 27380 KB Output is correct
5 Correct 45 ms 27596 KB Output is correct
6 Correct 178 ms 38012 KB Output is correct
7 Incorrect 13 ms 23748 KB Output isn't correct
8 Incorrect 16 ms 23764 KB Output isn't correct
9 Correct 12 ms 23752 KB Output is correct
10 Correct 12 ms 23884 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23752 KB Output is correct
14 Incorrect 12 ms 23728 KB Output isn't correct
15 Incorrect 13 ms 24020 KB Output isn't correct
16 Incorrect 12 ms 23892 KB Output isn't correct
17 Correct 12 ms 23792 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Correct 13 ms 23764 KB Output is correct
20 Correct 12 ms 23868 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Incorrect 13 ms 23892 KB Output isn't correct
23 Incorrect 56 ms 31660 KB Output isn't correct
24 Incorrect 72 ms 32712 KB Output isn't correct
25 Correct 53 ms 31264 KB Output is correct
26 Correct 46 ms 27388 KB Output is correct
27 Correct 46 ms 27340 KB Output is correct
28 Correct 46 ms 27728 KB Output is correct
29 Correct 142 ms 35436 KB Output is correct
30 Incorrect 74 ms 34808 KB Output isn't correct
31 Incorrect 76 ms 35012 KB Output isn't correct
32 Incorrect 69 ms 30408 KB Output isn't correct
33 Correct 74 ms 32064 KB Output is correct
34 Correct 45 ms 27408 KB Output is correct
35 Correct 45 ms 27372 KB Output is correct
36 Correct 46 ms 27644 KB Output is correct
37 Correct 157 ms 37964 KB Output is correct
38 Incorrect 70 ms 32156 KB Output isn't correct
39 Incorrect 66 ms 29864 KB Output isn't correct
40 Incorrect 75 ms 32480 KB Output isn't correct
41 Correct 61 ms 34428 KB Output is correct
42 Correct 47 ms 27216 KB Output is correct
43 Correct 44 ms 27312 KB Output is correct
44 Correct 46 ms 27716 KB Output is correct
45 Correct 117 ms 36360 KB Output is correct
46 Incorrect 76 ms 35420 KB Output isn't correct
47 Incorrect 72 ms 32496 KB Output isn't correct
48 Incorrect 79 ms 34756 KB Output isn't correct
49 Correct 51 ms 29180 KB Output is correct
50 Correct 47 ms 27628 KB Output is correct
51 Correct 46 ms 27596 KB Output is correct
52 Correct 45 ms 27396 KB Output is correct
53 Correct 130 ms 36056 KB Output is correct
54 Incorrect 74 ms 33576 KB Output isn't correct