oj.uz

Submission #555931

# Submission time Handle Problem Language Result Execution time Memory
555931 2022-05-01T20:26:49 Z new_acc Pipes (BOI13_pipes) C++14
74.0741 / 100
 205 ms 43084 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);
}
int dfs(int v){
    if(vis[v]) return 0;
    vis[v]=1;
    int sum=0;
    for(auto u:graf[v]){
        int curr=dfs(u.fi);
        sum+=curr,ans[u.se]=(curr<<1);
    }
    return 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;
    }
    int sum1=0,sum2=0;
    for(int i=1;i<c.size();i+=2) sum1-=t[c[i]];
    sum1<<=1;
    for(int i=0;i<c.size();i++) sum2-=t[c[i]];
    ans[val[c[0]]]=sum2-sum1;
    if(ans[val[c[0]]]&1) 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-=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-=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 12 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 14 ms 23788 KB Output is correct
4 Correct 79 ms 29900 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23788 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 13 ms 23816 KB Output is correct
10 Correct 14 ms 23892 KB Output is correct
11 Correct 13 ms 23788 KB Output is correct
12 Correct 14 ms 23808 KB Output is correct
13 Correct 57 ms 28884 KB Output is correct
14 Correct 78 ms 29696 KB Output is correct
15 Correct 79 ms 29916 KB Output is correct
16 Correct 59 ms 29216 KB Output is correct
17 Correct 70 ms 29940 KB Output is correct
18 Correct 65 ms 30084 KB Output is correct
19 Correct 83 ms 32548 KB Output is correct
20 Correct 13 ms 23764 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Correct 68 ms 29984 KB Output is correct
23 Correct 52 ms 28936 KB Output is correct
24 Correct 68 ms 29916 KB Output is correct
25 Correct 62 ms 29144 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23820 KB Output isn't correct
2 Incorrect 12 ms 23964 KB Output isn't correct
3 Correct 54 ms 32332 KB Output is correct
4 Correct 48 ms 29044 KB Output is correct
5 Correct 52 ms 29280 KB Output is correct
6 Correct 205 ms 43028 KB Output is correct
7 Incorrect 13 ms 23764 KB Output isn't correct
8 Incorrect 13 ms 23764 KB Output isn't correct
9 Correct 12 ms 23760 KB Output is correct
10 Correct 13 ms 23940 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Incorrect 14 ms 23816 KB Output isn't correct
15 Incorrect 13 ms 23892 KB Output isn't correct
16 Incorrect 13 ms 23892 KB Output isn't correct
17 Correct 13 ms 23892 KB Output is correct
18 Correct 14 ms 23880 KB Output is correct
19 Correct 12 ms 23764 KB Output is correct
20 Correct 12 ms 23832 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Incorrect 13 ms 23928 KB Output isn't correct
23 Incorrect 62 ms 32788 KB Output isn't correct
24 Incorrect 76 ms 33908 KB Output isn't correct
25 Correct 54 ms 32332 KB Output is correct
26 Correct 49 ms 29044 KB Output is correct
27 Correct 48 ms 28876 KB Output is correct
28 Correct 49 ms 29408 KB Output is correct
29 Correct 162 ms 40452 KB Output is correct
30 Incorrect 78 ms 36000 KB Output isn't correct
31 Incorrect 78 ms 36120 KB Output isn't correct
32 Incorrect 76 ms 31564 KB Output isn't correct
33 Correct 57 ms 33196 KB Output is correct
34 Correct 48 ms 29000 KB Output is correct
35 Correct 50 ms 29008 KB Output is correct
36 Correct 49 ms 29196 KB Output is correct
37 Correct 167 ms 43084 KB Output is correct
38 Incorrect 73 ms 33244 KB Output isn't correct
39 Incorrect 70 ms 31088 KB Output isn't correct
40 Incorrect 75 ms 33608 KB Output isn't correct
41 Correct 62 ms 35584 KB Output is correct
42 Correct 54 ms 28980 KB Output is correct
43 Correct 50 ms 28832 KB Output is correct
44 Correct 46 ms 29148 KB Output is correct
45 Correct 123 ms 41344 KB Output is correct
46 Incorrect 82 ms 36480 KB Output isn't correct
47 Incorrect 77 ms 33740 KB Output isn't correct
48 Incorrect 96 ms 35912 KB Output isn't correct
49 Correct 50 ms 30268 KB Output is correct
50 Correct 48 ms 29108 KB Output is correct
51 Correct 49 ms 29132 KB Output is correct
52 Correct 50 ms 28956 KB Output is correct
53 Correct 139 ms 41160 KB Output is correct
54 Incorrect 78 ms 34720 KB Output isn't correct