oj.uz

Submission #284702

# Submission time Handle Problem Language Result Execution time Memory
284702 2020-08-27T22:12:54 Z ScarletS Pipes (BOI13_pipes) C++17
33.7037 / 100
 1000 ms 131072 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
#define pii pair<int,int>
using namespace std;

const int MAXN = 100001;
stack<pii> edges[MAXN];
int score[MAXN],amount[MAXN],x;
ll cur[MAXN],t;
int ans[5*MAXN];
bool done[MAXN];
vector<int> circle;

void dfs(int c)
{
    done[c]=1;
    circle.push_back(c);
    while (sz(edges[c]))
    {
        if (done[edges[c].top().first])
            edges[c].pop();
        else
            dfs(edges[c].top().first);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m,u,v;
    cin>>n>>m;
    map<pii,int> vals;
    for (int i = 1; i <= n; ++i)
        cin>>score[i];
    for (int i = 0; i < m; ++i)
    {
        cin>>u>>v;
        edges[u].push({v,i});
        edges[v].push({u,i});
        vals[{u,v}]=i;
        vals[{v,u}]=i;
        ++amount[u];
        ++amount[v];
    }
    if (m>n)
    {
        cout<<"0\n";
        return 0;
    }
    stack<int> s;
    for (int i=1;i<=n;++i)
        if (amount[i]==1)
            s.push(i);
    while (sz(s))
    {
        ++x;
        u=s.top();
        s.pop();
        while (done[edges[u].top().first])
            edges[u].pop();
        v=edges[u].top().first;
        ans[edges[u].top().second]=score[u]-cur[u];
        cur[u]+=ans[edges[u].top().second];
        cur[v]+=ans[edges[u].top().second];
        //ans[edges[u].top().second]<<=1;
    }
    if (m==n-1)
    {
        for (int i=0;i<m;++i)
            cout<<ans[i]*2<<"\n";
        return 0;
    }
    if ((n-x+1)&1)
    {
        cout<<"0\n";
        return 0;
    }
    for (int i=1;i<=n;++i)
    {
        while (sz(edges[u])&&done[edges[u].top().first])
            edges[u].pop();
        if (sz(edges[u]))
            x=u;
    }
    dfs(x);
    /**for (int i : circle)
        cout<<i<<" ";
    cout<<"\n";**/
    for (int i=0;i<sz(circle);++i)
    {
        //cout<<"nigga\n";
        if (i&1)
            t-=score[circle[i]];
        else
            t+=score[circle[i]];
    }
    //cout<<"t="<<t<<"\n";
    ans[vals[{circle[0],circle.back()}]]=t/2;
    ans[vals[{circle[0],circle[1]}]]=score[circle[0]]-ans[vals[{circle[0],circle.back()}]];
    for (int i=1;i+1<sz(circle);++i)
    {
        //cout<<"ans[vals[{"<<circle[i]<<","<<circle[i+1]<<"}] = "<<score[circle[i]]<<" - "<<ans[vals[{circle[i],circle[i-1]}]]<<"\n";
        ans[vals[{circle[i],circle[i+1]}]]=score[circle[i]]-ans[vals[{circle[i],circle[i-1]}]];
    }
    for (int i=0;i<m;++i)
        cout<<ans[i]*2<<"\n";
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 67704 KB Output isn't correct
2 Incorrect 55 ms 67704 KB Output isn't correct
3 Incorrect 59 ms 67832 KB Output isn't correct
4 Incorrect 238 ms 84232 KB Output isn't correct
5 Incorrect 55 ms 67704 KB Output isn't correct
6 Incorrect 58 ms 67704 KB Output isn't correct
7 Incorrect 54 ms 67744 KB Output isn't correct
8 Incorrect 56 ms 67704 KB Output isn't correct
9 Incorrect 55 ms 67832 KB Output isn't correct
10 Incorrect 54 ms 67832 KB Output isn't correct
11 Incorrect 53 ms 67832 KB Output isn't correct
12 Incorrect 54 ms 67832 KB Output isn't correct
13 Incorrect 197 ms 80760 KB Output isn't correct
14 Incorrect 227 ms 83340 KB Output isn't correct
15 Incorrect 236 ms 84268 KB Output isn't correct
16 Incorrect 198 ms 81784 KB Output isn't correct
17 Incorrect 247 ms 84300 KB Output isn't correct
18 Incorrect 231 ms 84284 KB Output isn't correct
19 Incorrect 241 ms 83960 KB Output isn't correct
20 Incorrect 52 ms 67704 KB Output isn't correct
21 Incorrect 53 ms 67832 KB Output isn't correct
22 Incorrect 233 ms 84216 KB Output isn't correct
23 Incorrect 211 ms 80836 KB Output isn't correct
24 Incorrect 241 ms 84344 KB Output isn't correct
25 Incorrect 201 ms 81528 KB Output isn't correct

Subtask #2
33.7037037037 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 67704 KB Output isn't correct
2 Incorrect 55 ms 67832 KB Output isn't correct
3 Incorrect 386 ms 89584 KB Output isn't correct
4 Correct 217 ms 82688 KB Output is correct
5 Correct 205 ms 82168 KB Output is correct
6 Execution timed out 1097 ms 131072 KB Time limit exceeded
7 Incorrect 51 ms 67704 KB Output isn't correct
8 Incorrect 52 ms 67704 KB Output isn't correct
9 Incorrect 51 ms 67704 KB Output isn't correct
10 Correct 52 ms 67652 KB Output is correct
11 Correct 54 ms 67704 KB Output is correct
12 Correct 56 ms 67832 KB Output is correct
13 Correct 53 ms 67704 KB Output is correct
14 Incorrect 52 ms 67704 KB Output isn't correct
15 Incorrect 53 ms 67832 KB Output isn't correct
16 Incorrect 53 ms 67960 KB Output isn't correct
17 Correct 54 ms 67960 KB Output is correct
18 Correct 54 ms 67864 KB Output is correct
19 Correct 61 ms 67960 KB Output is correct
20 Correct 53 ms 67832 KB Output is correct
21 Correct 54 ms 68088 KB Output is correct
22 Incorrect 55 ms 67892 KB Output isn't correct
23 Incorrect 299 ms 85908 KB Output isn't correct
24 Incorrect 389 ms 90228 KB Output isn't correct
25 Incorrect 369 ms 89580 KB Output isn't correct
26 Correct 232 ms 82556 KB Output is correct
27 Correct 227 ms 82424 KB Output is correct
28 Correct 267 ms 83192 KB Output is correct
29 Correct 907 ms 123640 KB Output is correct
30 Incorrect 380 ms 89200 KB Output isn't correct
31 Incorrect 376 ms 89748 KB Output isn't correct
32 Incorrect 239 ms 83884 KB Output isn't correct
33 Incorrect 394 ms 90268 KB Output isn't correct
34 Correct 221 ms 82552 KB Output is correct
35 Correct 219 ms 82552 KB Output is correct
36 Correct 211 ms 82808 KB Output is correct
37 Execution timed out 1104 ms 131072 KB Time limit exceeded
38 Incorrect 369 ms 89468 KB Output isn't correct
39 Incorrect 388 ms 90736 KB Output isn't correct
40 Incorrect 395 ms 90384 KB Output isn't correct
41 Incorrect 360 ms 89712 KB Output isn't correct
42 Correct 215 ms 82524 KB Output is correct
43 Correct 228 ms 82552 KB Output is correct
44 Correct 220 ms 82296 KB Output is correct
45 Correct 991 ms 129016 KB Output is correct
46 Incorrect 220 ms 83696 KB Output isn't correct
47 Incorrect 223 ms 83832 KB Output isn't correct
48 Incorrect 237 ms 83832 KB Output isn't correct
49 Correct 215 ms 82944 KB Output is correct
50 Correct 213 ms 82552 KB Output is correct
51 Correct 212 ms 82700 KB Output is correct
52 Correct 211 ms 82256 KB Output is correct
53 Execution timed out 1059 ms 130448 KB Time limit exceeded
54 Incorrect 370 ms 89552 KB Output isn't correct