oj.uz

Submission #221957

# Submission time Handle Problem Language Result Execution time Memory
221957 2020-04-11T15:28:58 Z XmtosX Pipes (BOI13_pipes) C++17
38.8889 / 100
 258 ms 17400 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,o;
long long a[N],sz[N],ans[N];
vector <pair<int,int> > v[N];
queue<int> q;
bool vis[N];
long long sum (int x)
{
    vis[x]=true;
    long long here=0;
    bool yes=false;
    for (int i=0;i<v[x].size();i++)
    {
        if (!vis[v[x][i].first])
        {
            yes=true;
            here=sum(v[x][i].first);
            break;
        }
    }
    vis[x]=false;
    return here+a[x];
}
long long dfs1 (int x,long long last)
{
    vis[x]=true;
    bool yes=false;
    long long here=0;
    for (int i=0;i<v[x].size();i++)
    {
        if (!vis[v[x][i].first])
        {
            here=dfs1(v[x][i].first,a[v[x][i].first]-last);
            yes=true;
            break;
        }
    }
    vis[x]=false;
    return here+last;
}
void dfs2 (int x)
{
    vis[x]=true;
    bool yes=false;
    for (int i=0;i<v[x].size();i++)
    {
        if (!vis[v[x][i].first])
        {
            a[v[x][i].first]-=a[x];
            ans[v[x][i].second]=a[x];
            dfs2(v[x][i].first);
            yes=true;
            break;
        }
    }
    if (!yes)
    {
        for (int i=0;i<v[x].size();i++)
        {
            if (v[x][i].first==o)
            {
                ans[v[x][i].second]=a[x];
                break;
            }
        }
    }
    vis[x]=false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for (int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back({b,i});
        v[b].push_back({a,i});
    }
    if (m>n)
    {
        cout <<0;
        return 0;
    }
    for (int i=1;i<=n;i++)
    {
        sz[i]=v[i].size();
        if (v[i].size()==1)
        {
            q.push(i);
        }
    }
    int cnt=n;
    while (!q.empty())
    {
        int x= q.front();
        q.pop();
        cnt--;
        vis[x]=true;
        for (int i=0;i<v[x].size();i++)
        {
            int nxt=v[x][i].first;
            int idx=v[x][i].second;
            if (!vis[nxt])
            {
                ans[idx]=a[x];
                a[nxt]-=a[x];
                if (idx==1)
                sz[nxt]--;
                if (sz[nxt]==1)
                    q.push(nxt);
            }
        }
    }
    if (cnt%2==0&&cnt)
    {
        cout <<0;
        return 0;
    }
    for (int i=1;i<=n;i++)
    {
        if (!vis[i])
        {
            o=i;
            long long x=sum(i);
            x/=2;
            long long y=dfs1(i,0);
            a[i]= x-y;
            dfs2(i);
            break;
        }
    }
    for (int i=0;i<m;i++)
        printf("%lld\n",ans[i]*2ll);
    return 0;
}
/*
4 3
-1
1
-3
1
1 2
1 3
1 4

4 5
1
2
1
2
1 2
2 3
3 4
4 1
1 3

3 3
1
15
-4
1 2
2 3
3 1
*/

Compilation message

pipes.cpp: In function 'long long int sum(int)':
pipes.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
pipes.cpp:13:10: warning: variable 'yes' set but not used [-Wunused-but-set-variable]
     bool yes=false;
          ^~~
pipes.cpp: In function 'long long int dfs1(int, long long int)':
pipes.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
pipes.cpp:29:10: warning: variable 'yes' set but not used [-Wunused-but-set-variable]
     bool yes=false;
          ^~~
pipes.cpp: In function 'void dfs2(int)':
pipes.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
pipes.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[x].size();i++)
                      ~^~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[x].size();i++)
                      ~^~~~~~~~~~~~
pipes.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
pipes.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
         ~~~~~^~~~~~~~~~~~~~
pipes.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2688 KB Output isn't correct
2 Incorrect 6 ms 2688 KB Output isn't correct
3 Incorrect 7 ms 2816 KB Output isn't correct
4 Incorrect 81 ms 9464 KB Output isn't correct
5 Incorrect 6 ms 2688 KB Output isn't correct
6 Incorrect 6 ms 2688 KB Output isn't correct
7 Incorrect 7 ms 2688 KB Output isn't correct
8 Incorrect 6 ms 2688 KB Output isn't correct
9 Incorrect 6 ms 2688 KB Output isn't correct
10 Incorrect 6 ms 2816 KB Output isn't correct
11 Incorrect 6 ms 2816 KB Output isn't correct
12 Incorrect 6 ms 2688 KB Output isn't correct
13 Incorrect 57 ms 7928 KB Output isn't correct
14 Incorrect 73 ms 9208 KB Output isn't correct
15 Incorrect 92 ms 9616 KB Output isn't correct
16 Incorrect 57 ms 8184 KB Output isn't correct
17 Incorrect 82 ms 9464 KB Output isn't correct
18 Incorrect 77 ms 9592 KB Output isn't correct
19 Incorrect 73 ms 8696 KB Output isn't correct
20 Incorrect 6 ms 2688 KB Output isn't correct
21 Incorrect 6 ms 2816 KB Output isn't correct
22 Incorrect 68 ms 9208 KB Output isn't correct
23 Incorrect 53 ms 7800 KB Output isn't correct
24 Incorrect 66 ms 9208 KB Output isn't correct
25 Incorrect 65 ms 8444 KB Output isn't correct

Subtask #2
38.8888888889 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Incorrect 6 ms 2688 KB Output isn't correct
3 Incorrect 74 ms 8824 KB Output isn't correct
4 Correct 59 ms 6904 KB Output is correct
5 Correct 61 ms 7032 KB Output is correct
6 Correct 241 ms 17400 KB Output is correct
7 Incorrect 6 ms 2816 KB Output isn't correct
8 Correct 6 ms 2688 KB Output is correct
9 Incorrect 6 ms 2688 KB Output isn't correct
10 Correct 6 ms 2688 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 6 ms 2688 KB Output is correct
13 Correct 6 ms 2688 KB Output is correct
14 Incorrect 6 ms 2688 KB Output isn't correct
15 Incorrect 7 ms 2816 KB Output isn't correct
16 Incorrect 7 ms 2816 KB Output isn't correct
17 Correct 6 ms 2816 KB Output is correct
18 Correct 6 ms 2688 KB Output is correct
19 Correct 6 ms 2688 KB Output is correct
20 Correct 7 ms 2816 KB Output is correct
21 Correct 7 ms 2816 KB Output is correct
22 Incorrect 6 ms 2688 KB Output isn't correct
23 Incorrect 72 ms 8312 KB Output isn't correct
24 Incorrect 85 ms 9592 KB Output isn't correct
25 Incorrect 74 ms 8824 KB Output isn't correct
26 Correct 65 ms 6908 KB Output is correct
27 Correct 66 ms 6732 KB Output is correct
28 Correct 80 ms 7160 KB Output is correct
29 Correct 214 ms 14784 KB Output is correct
30 Incorrect 107 ms 9924 KB Output isn't correct
31 Incorrect 80 ms 8672 KB Output isn't correct
32 Incorrect 71 ms 9080 KB Output isn't correct
33 Incorrect 99 ms 10080 KB Output isn't correct
34 Correct 67 ms 6812 KB Output is correct
35 Correct 87 ms 6904 KB Output is correct
36 Correct 97 ms 7136 KB Output is correct
37 Correct 258 ms 17376 KB Output is correct
38 Incorrect 94 ms 8952 KB Output isn't correct
39 Incorrect 92 ms 9336 KB Output isn't correct
40 Incorrect 84 ms 9288 KB Output isn't correct
41 Incorrect 79 ms 8696 KB Output isn't correct
42 Correct 77 ms 6792 KB Output is correct
43 Correct 66 ms 6776 KB Output is correct
44 Correct 68 ms 7028 KB Output is correct
45 Correct 220 ms 15624 KB Output is correct
46 Incorrect 66 ms 8312 KB Output isn't correct
47 Incorrect 76 ms 8872 KB Output isn't correct
48 Incorrect 66 ms 8440 KB Output isn't correct
49 Correct 68 ms 8824 KB Output is correct
50 Correct 69 ms 7160 KB Output is correct
51 Correct 72 ms 7008 KB Output is correct
52 Correct 66 ms 6776 KB Output is correct
53 Correct 210 ms 15352 KB Output is correct
54 Incorrect 75 ms 9212 KB Output isn't correct