oj.uz

Submission #885546

# Submission time Handle Problem Language Result Execution time Memory
885546 2023-12-10T03:52:37 Z 8pete8 Pipes (BOI13_pipes) C++17
72.7778 / 100
 285 ms 48984 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
const int mod=1e9+7,mxn=5e5+5,lg=30,inf=1e18,minf=-1e18;
int ans[mxn+10],val[mxn+10],up[mxn+10],curval[mxn+10];
vector<pii>adj[mxn+10];
bitset<mxn+10>vis;
bool yes=false;
void solve(int cur,int p){
    if(vis[cur])return void(yes=true);
    vis[cur]=true;
    bool leaf=true;
    for(auto i:adj[cur])if(i.f!=p)leaf=false;
    if(leaf){
        ans[up[cur]]+=val[cur];
        curval[p]+=val[cur];
        return;
    }
    for(auto i:adj[cur]){
        if(i.f==p)continue;
        up[i.f]=i.s;
        solve(i.f,cur);
    }
    if(cur==1)return;
    ans[up[cur]]+=(val[cur]-curval[cur]);
    curval[p]+=(val[cur]-curval[cur]);
}
vector<ppii>path;
int deg[mxn+10],sum,cnt=0;
int start=1;
void solve2(int cur,int p){
    if(vis[cur])return;
    cnt++;
    sum+=(val[cur]-curval[cur])*((cnt%2)?1:-1);
    vis[cur]=true;
    for(auto i:adj[cur]){
        if(i.f==start&&i.f!=p)path.pb({i.s,{i.f,cur}});
        if(i.f==p||vis[i.f])continue;
        up[i.f]=i.s;
        path.pb({i.s,{i.f,cur}});
        solve2(i.f,cur);
    }
}
int32_t main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>val[i];
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
    }
    if(m>n){
        cout<<0;
        return 0;
    }
    if(m==n-1){
        solve(1,-1);
        for(int i=0;i<m;i++)cout<<2*ans[i]<<'\n';
        return 0;
    }
    stack<int>st;
    for(int i=1;i<=n;i++){
        if(adj[i].size()==1)st.push(i);
        deg[i]=adj[i].size();
    }
    cnt=0;
    while(!st.empty()){
        vis[st.top()]=true;
        for(auto i:adj[st.top()]){
            if(vis[i.f])continue;
            deg[i.f]--;
            ans[i.s]+=val[st.top()];-curval[st.top()];
            curval[i.f]+=val[st.top()];-curval[st.top()];
            if(deg[i.f]==1)st.push(i.f);
        }
        st.pop();
        cnt++;
    }
    for(int i=1;i<=n;i++)if(!vis[i])start=i;
    if((n-cnt)%2==0){
        cout<<0;
        return 0;
    }
    cnt=0;
    solve2(start,-1);
    sum/=2;
    reverse(all(path));
    for(int i=0;i<path.size();i++){
        if(i==0){
            ans[path[i].f]+=sum;
            curval[path[i].s.f]+=sum;
            curval[path[i].s.s]+=sum;
        }
        else{
            ans[path[i].f]+=val[path[i].s.f]-curval[path[i].s.f];
            curval[path[i].s.f]+=val[path[i].s.f]-curval[path[i].s.f];
            curval[path[i].s.s]+=val[path[i].s.f]-curval[path[i].s.f];
        }
    }
    for(int i=0;i<m;i++)cout<<2*ans[i]<<'\n';
}

Compilation message

pipes.cpp: In function 'int32_t main()':
pipes.cpp:103:37: warning: value computed is not used [-Wunused-value]
  103 |             ans[i.s]+=val[st.top()];-curval[st.top()];
      |                                     ^~~~~~~~~~~~~~~~~
pipes.cpp:104:40: warning: value computed is not used [-Wunused-value]
  104 |             curval[i.f]+=val[st.top()];-curval[st.top()];
      |                                        ^~~~~~~~~~~~~~~~~
pipes.cpp:119:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i=0;i<path.size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 88 ms 27828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 4 ms 20956 KB Output is correct
7 Correct 5 ms 20972 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20916 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 5 ms 20988 KB Output is correct
13 Correct 68 ms 26584 KB Output is correct
14 Correct 76 ms 27476 KB Output is correct
15 Correct 83 ms 27936 KB Output is correct
16 Correct 77 ms 26964 KB Output is correct
17 Correct 80 ms 27908 KB Output is correct
18 Correct 81 ms 27988 KB Output is correct
19 Correct 88 ms 31052 KB Output is correct
20 Correct 4 ms 20824 KB Output is correct
21 Correct 4 ms 20828 KB Output is correct
22 Correct 81 ms 27972 KB Output is correct
23 Correct 65 ms 26572 KB Output is correct
24 Correct 81 ms 27988 KB Output is correct
25 Correct 68 ms 26704 KB Output is correct

Subtask #2
42.7777777778 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18780 KB Output isn't correct
2 Incorrect 4 ms 18936 KB Output isn't correct
3 Correct 70 ms 26312 KB Output is correct
4 Correct 77 ms 23512 KB Output is correct
5 Correct 69 ms 23376 KB Output is correct
6 Correct 285 ms 48840 KB Output is correct
7 Incorrect 3 ms 18780 KB Output isn't correct
8 Incorrect 3 ms 18780 KB Output isn't correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Incorrect 3 ms 18776 KB Output isn't correct
15 Incorrect 4 ms 19032 KB Output isn't correct
16 Incorrect 5 ms 19032 KB Output isn't correct
17 Correct 5 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 4 ms 16732 KB Output is correct
20 Correct 4 ms 16732 KB Output is correct
21 Correct 4 ms 16988 KB Output is correct
22 Incorrect 4 ms 16728 KB Output isn't correct
23 Incorrect 76 ms 37512 KB Output isn't correct
24 Incorrect 93 ms 36976 KB Output isn't correct
25 Correct 69 ms 26192 KB Output is correct
26 Correct 77 ms 23568 KB Output is correct
27 Correct 70 ms 23316 KB Output is correct
28 Correct 73 ms 23892 KB Output is correct
29 Correct 254 ms 42324 KB Output is correct
30 Incorrect 79 ms 26452 KB Output isn't correct
31 Incorrect 101 ms 40920 KB Output isn't correct
32 Incorrect 88 ms 32528 KB Output isn't correct
33 Correct 77 ms 26648 KB Output is correct
34 Correct 71 ms 23380 KB Output is correct
35 Correct 72 ms 23476 KB Output is correct
36 Correct 72 ms 23492 KB Output is correct
37 Correct 271 ms 48984 KB Output is correct
38 Incorrect 96 ms 39156 KB Output isn't correct
39 Incorrect 73 ms 26852 KB Output isn't correct
40 Incorrect 92 ms 37044 KB Output isn't correct
41 Incorrect 97 ms 40940 KB Output isn't correct
42 Correct 71 ms 23492 KB Output is correct
43 Correct 79 ms 23616 KB Output is correct
44 Correct 69 ms 23216 KB Output is correct
45 Correct 216 ms 45792 KB Output is correct
46 Incorrect 76 ms 26196 KB Output isn't correct
47 Incorrect 91 ms 26816 KB Output isn't correct
48 Incorrect 100 ms 40948 KB Output isn't correct
49 Correct 69 ms 26456 KB Output is correct
50 Correct 73 ms 23548 KB Output is correct
51 Correct 71 ms 23380 KB Output is correct
52 Correct 75 ms 23816 KB Output is correct
53 Correct 230 ms 45136 KB Output is correct
54 Incorrect 75 ms 26404 KB Output isn't correct