oj.uz

Submission #78685

# Submission time Handle Problem Language Result Execution time Memory
78685 2018-10-07T13:59:24 Z Charis02 Pipes (BOI13_pipes) C++14
88.3333 / 100
 270 ms 29428 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 100004
#define INF 1e9+7

using namespace std;

ll n,m,ar[N],val[N];
bool vis[N],cycle;
vector < vector < pi > > graph(N);
vector < pi > neo;

void solvetree(ll cur,ll par,ll edge)
{
    rep(i,0,graph[cur].size())
    {
        ll v = graph[cur][i].first;

        if(v == par)
            continue;

        solvetree(v,cur,graph[cur][i].second);

        ar[cur] -= val[graph[cur][i].second];
    }

//    cout << cur << " " << par << " " << edge << " " << ar[cur] <<endl;

    val[edge] = ar[cur];

    return;
}

bool solvemn(ll cur,ll par,ll edge)
{
    if(vis[cur])
    {
        if(!cycle)
            neo.push_back(mp(cur,edge));

        cycle = true;
        return true;
    }

    bool found= false;
    vis[cur] = true;

    rep(i,0,graph[cur].size())
    {
        ll v = graph[cur][i].first;

        if(v == par)
            continue;

        if(solvemn(v,cur,graph[cur][i].second))
        {
            if(!neo.empty() && cur == neo[0].first)
                continue;

            neo.push_back(mp(cur,edge));
            found = true;
        }
        else
            ar[cur] -= val[graph[cur][i].second];
    }

    if(!found)
        val[edge] = ar[cur];

    return found;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> m;

    rep(i,1,n+1)
    {
        cin >> ar[i];
    }

    rep(i,0,m)
    {
        ll a,b;
        cin >> a >> b;
        graph[a].push_back(mp(b,i));
        graph[b].push_back(mp(a,i));
    }

    if(m > n)
    {
        cout << 0 << endl;
        return 0;
    }
    else if(m == n-1)
    {
        solvetree(1,1,m);

        rep(i,0,m)
        {
            cout << 2*val[i] << endl;
        }
    }
    else
    {
        solvemn(1,1,m);

        if((neo.size())%2==0)
        {
            cout << 0 << endl;
        }
        else
        {
            ll s = 0;

            rep(i,0,neo.size())
            {
                s += ar[neo[i].first]*pow(-1,i%2);
            }

            val[neo[neo.size()-1].second] = s/2;
            val[neo[0].second] = ar[neo[0].first] - s/2;

            rep(i,1,neo.size()-1)
            {
                val[neo[i].second] = -val[neo[i-1].second] + ar[neo[i].first];
            }

            rep(i,0,m)
            {
                cout << 2*val[i] << endl;
            }
        }
    }

    return 0;
}

/*
3 3
1 3 2
1 2
1 3
2 3
*/

Compilation message

pipes.cpp: In function 'void solvetree(long long int, long long int, long long int)':
pipes.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
pipes.cpp:26:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
pipes.cpp:26:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
pipes.cpp: In function 'bool solvemn(long long int, long long int, long long int)':
pipes.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
pipes.cpp:59:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
pipes.cpp:59:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
pipes.cpp: In function 'int main()':
pipes.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
pipes.cpp:129:17:
             rep(i,0,neo.size())
                 ~~~~~~~~~~~~~~      
pipes.cpp:129:13: note: in expansion of macro 'rep'
             rep(i,0,neo.size())
             ^~~
pipes.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
pipes.cpp:137:17:
             rep(i,1,neo.size()-1)
                 ~~~~~~~~~~~~~~~~    
pipes.cpp:137:13: note: in expansion of macro 'rep'
             rep(i,1,neo.size()-1)
             ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2824 KB Output is correct
3 Correct 6 ms 2848 KB Output is correct
4 Correct 242 ms 9888 KB Output is correct
5 Correct 4 ms 9888 KB Output is correct
6 Correct 4 ms 9888 KB Output is correct
7 Correct 5 ms 9888 KB Output is correct
8 Correct 4 ms 9888 KB Output is correct
9 Correct 6 ms 9888 KB Output is correct
10 Correct 7 ms 9888 KB Output is correct
11 Correct 6 ms 9888 KB Output is correct
12 Correct 6 ms 9888 KB Output is correct
13 Correct 183 ms 9888 KB Output is correct
14 Correct 221 ms 9888 KB Output is correct
15 Correct 234 ms 10144 KB Output is correct
16 Correct 191 ms 10144 KB Output is correct
17 Correct 242 ms 10144 KB Output is correct
18 Correct 241 ms 10144 KB Output is correct
19 Correct 244 ms 13448 KB Output is correct
20 Correct 4 ms 13448 KB Output is correct
21 Correct 6 ms 13448 KB Output is correct
22 Correct 232 ms 13448 KB Output is correct
23 Correct 177 ms 13448 KB Output is correct
24 Correct 246 ms 13448 KB Output is correct
25 Correct 187 ms 13448 KB Output is correct

Subtask #2
58.3333333333 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13448 KB Output isn't correct
2 Correct 6 ms 13448 KB Output is correct
3 Correct 90 ms 15492 KB Output is correct
4 Correct 57 ms 15492 KB Output is correct
5 Correct 54 ms 15492 KB Output is correct
6 Correct 250 ms 29404 KB Output is correct
7 Incorrect 4 ms 29404 KB Output isn't correct
8 Correct 4 ms 29404 KB Output is correct
9 Correct 5 ms 29404 KB Output is correct
10 Correct 4 ms 29404 KB Output is correct
11 Correct 4 ms 29404 KB Output is correct
12 Correct 4 ms 29404 KB Output is correct
13 Correct 4 ms 29404 KB Output is correct
14 Incorrect 4 ms 29404 KB Output isn't correct
15 Correct 6 ms 29404 KB Output is correct
16 Correct 6 ms 29404 KB Output is correct
17 Correct 6 ms 29404 KB Output is correct
18 Correct 4 ms 29404 KB Output is correct
19 Correct 5 ms 29404 KB Output is correct
20 Correct 4 ms 29404 KB Output is correct
21 Correct 5 ms 29404 KB Output is correct
22 Incorrect 6 ms 29404 KB Output isn't correct
23 Correct 196 ms 29404 KB Output is correct
24 Correct 245 ms 29404 KB Output is correct
25 Correct 79 ms 29404 KB Output is correct
26 Correct 67 ms 29404 KB Output is correct
27 Correct 66 ms 29404 KB Output is correct
28 Correct 100 ms 29404 KB Output is correct
29 Correct 246 ms 29404 KB Output is correct
30 Incorrect 241 ms 29404 KB Output isn't correct
31 Correct 270 ms 29404 KB Output is correct
32 Correct 225 ms 29404 KB Output is correct
33 Correct 92 ms 29404 KB Output is correct
34 Correct 68 ms 29404 KB Output is correct
35 Correct 57 ms 29404 KB Output is correct
36 Correct 58 ms 29404 KB Output is correct
37 Correct 261 ms 29428 KB Output is correct
38 Correct 251 ms 29428 KB Output is correct
39 Incorrect 229 ms 29428 KB Output isn't correct
40 Incorrect 245 ms 29428 KB Output isn't correct
41 Correct 80 ms 29428 KB Output is correct
42 Correct 57 ms 29428 KB Output is correct
43 Correct 60 ms 29428 KB Output is correct
44 Correct 55 ms 29428 KB Output is correct
45 Correct 200 ms 29428 KB Output is correct
46 Correct 269 ms 29428 KB Output is correct
47 Incorrect 233 ms 29428 KB Output isn't correct
48 Correct 249 ms 29428 KB Output is correct
49 Correct 80 ms 29428 KB Output is correct
50 Correct 61 ms 29428 KB Output is correct
51 Correct 59 ms 29428 KB Output is correct
52 Correct 59 ms 29428 KB Output is correct
53 Correct 236 ms 29428 KB Output is correct
54 Incorrect 251 ms 29428 KB Output isn't correct