oj.uz

Submission #548001

# Submission time Handle Problem Language Result Execution time Memory
548001 2022-04-12T08:08:37 Z Amylopectin Pipes (BOI13_pipes) C++14
74.0741 / 100
 208 ms 53128 KB 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
const long long mxn = 6e5 + 10;
struct we
{
    long long to,num;
};
queue<long long> qu;
vector<struct we> pa[mxn] = {};
long long patva[mxn] = {},nva[mxn] = {},ind[mxn] = {},u[mxn] = {},upa[mxn] = {},sta = 0,li[mxn] = {},pnu[mxn] = {};
long long re(long long cn,long long be,long long cou)
{
    long long i,j,fn,cnu;
    u[cn] = 1;
    li[cou] = cn;
    for(i=0; i<pa[cn].size(); i++)
    {
        fn = pa[cn][i].to;
        cnu = pa[cn][i].num;
        if(cou > 1 && fn == li[0])
        {
            pnu[cou] = cnu;
        }
        if(u[fn] == 1)
            continue;
        pnu[cou] = cnu;
        re(fn,cn,cou+1);
    }
}
int main()
{
    long long i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
    scanf("%lld %lld",&n,&m);
    for(i=1; i<=n; i++)
    {
        scanf("%lld",&nva[i]);
    }
    for(j=0; j<m; j++)
    {
        scanf("%lld %lld",&cn,&cm);
        pa[cn].push_back({cm,j});
        pa[cm].push_back({cn,j});
        ind[cn] ++;
        ind[cm] ++;
    }
    if(m > n)
    {
        printf("0\n");
        return 0;
    }
    for(i=1; i<=n; i++)
    {
        if(ind[i] == 1)
        {
            qu.push(i);
            u[i] = 1;
            cou ++;
        }
    }
    if(m == n-1)
    {
        while(!qu.empty())
        {
            cn = qu.front();
            qu.pop();
//            of = 1;
            for(i=0; i<pa[cn].size(); i++)
            {
                fn = pa[cn][i].to;
                cnu = pa[cn][i].num;
                if(upa[cnu] == 1)
                    continue;
                upa[cnu] = 1;
//                of = 0;
                ind[fn] --;
                patva[cnu] = nva[cn];
                nva[fn] -= nva[cn];
                if(u[fn] == 1)
                {
                    if(nva[fn] != 0)
                    {
                        printf("0\n");
                        return 0;
                    }
                }
                if(ind[fn] == 1)
                {
                    u[fn] = 1;
                    qu.push(fn);
                    cou ++;
                }
            }
//            if(of == 1)
//            {
//                if()
//            }
        }
        for(i=0; i<m; i++)
        {
            printf("%lld\n",patva[i] * 2);
        }
    }
    else
    {
        while(!qu.empty())
        {
            cn = qu.front();
            qu.pop();
            for(i=0; i<pa[cn].size(); i++)
            {
                fn = pa[cn][i].to;
                cnu = pa[cn][i].num;
                if(upa[cnu] == 1)
                    continue;
                upa[cnu] = 1;
                ind[fn] --;
                patva[cnu] = nva[cn];
                nva[fn] -= nva[cn];
                if(ind[fn] == 1)
                {
                    u[fn] = 1;
                    qu.push(fn);
                    cou ++;
                }
            }
        }
        cyn = n-cou;
        if(cyn%2 == 0)
        {
            printf("0\n");
            return 0;
        }
        su = 0;
        for(i=1; i<=n; i++)
        {
            if(u[i] == 0)
            {
                su += nva[i];
                st = i;
            }
        }
        if(su % 2 == 1)
        {
            printf("0\n");
            return 0;
        }
        re(st,-1,0);
        csu = 0;
        for(i=cyn-1; i>0; i-=2)
        {
            csu += nva[li[i]];
        }
        patva[pnu[0]] = su/2 - csu;
        for(i=1; i<cyn; i++)
        {
            patva[pnu[i]] = nva[li[i]] - patva[pnu[i-1]];
        }
        if(patva[pnu[0]] + patva[pnu[cyn-1]] != nva[li[0]])
        {
            printf("0\n");
            return 0;
        }
        for(i=0; i<m; i++)
        {
            printf("%lld\n",patva[i] * 2);
        }
    }
    return 0;
}

Compilation message

pipes.cpp: In function 'long long int re(long long int, long long int, long long int)':
pipes.cpp:20:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(i=0; i<pa[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~
pipes.cpp:17:17: warning: unused variable 'j' [-Wunused-variable]
   17 |     long long i,j,fn,cnu;
      |                 ^
pipes.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
   33 | }
      | ^
pipes.cpp: In function 'int main()':
pipes.cpp:71:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(i=0; i<pa[cn].size(); i++)
      |                      ~^~~~~~~~~~~~~~
pipes.cpp:113:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(i=0; i<pa[cn].size(); i++)
      |                      ~^~~~~~~~~~~~~~
pipes.cpp:36:32: warning: unused variable 'fm' [-Wunused-variable]
   36 |     long long i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
      |                                ^~
pipes.cpp:36:47: warning: unused variable 'of' [-Wunused-variable]
   36 |     long long i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
      |                                               ^~
pipes.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
pipes.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%lld",&nva[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%lld %lld",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
pipes.cpp:151:11: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  151 |         re(st,-1,0);
      |         ~~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14408 KB Output is correct
3 Correct 9 ms 14524 KB Output is correct
4 Correct 77 ms 24780 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct
7 Correct 7 ms 14400 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 62 ms 22180 KB Output is correct
14 Correct 74 ms 23672 KB Output is correct
15 Correct 78 ms 24240 KB Output is correct
16 Correct 68 ms 22732 KB Output is correct
17 Correct 78 ms 24200 KB Output is correct
18 Correct 79 ms 24396 KB Output is correct
19 Correct 82 ms 24024 KB Output is correct
20 Correct 8 ms 14452 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct
22 Correct 83 ms 24312 KB Output is correct
23 Correct 63 ms 22276 KB Output is correct
24 Correct 79 ms 24312 KB Output is correct
25 Correct 64 ms 22548 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 29052 KB Execution killed with signal 11
2 Runtime error 20 ms 29264 KB Execution killed with signal 11
3 Correct 61 ms 23116 KB Output is correct
4 Correct 54 ms 21092 KB Output is correct
5 Correct 56 ms 20964 KB Output is correct
6 Correct 205 ms 41900 KB Output is correct
7 Runtime error 21 ms 29004 KB Execution killed with signal 11
8 Runtime error 21 ms 29048 KB Execution killed with signal 11
9 Correct 8 ms 14412 KB Output is correct
10 Correct 8 ms 14432 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14316 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Runtime error 19 ms 28992 KB Execution killed with signal 11
15 Runtime error 21 ms 29260 KB Execution killed with signal 11
16 Runtime error 21 ms 29152 KB Execution killed with signal 11
17 Correct 8 ms 14520 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 8 ms 14420 KB Output is correct
21 Correct 8 ms 14548 KB Output is correct
22 Runtime error 21 ms 29176 KB Execution killed with signal 11
23 Runtime error 72 ms 47624 KB Execution killed with signal 11
24 Runtime error 89 ms 51248 KB Execution killed with signal 11
25 Correct 66 ms 23216 KB Output is correct
26 Correct 55 ms 21164 KB Output is correct
27 Correct 55 ms 21024 KB Output is correct
28 Correct 59 ms 21324 KB Output is correct
29 Correct 171 ms 36532 KB Output is correct
30 Runtime error 88 ms 50028 KB Execution killed with signal 11
31 Runtime error 88 ms 53128 KB Execution killed with signal 11
32 Runtime error 92 ms 49040 KB Execution killed with signal 11
33 Correct 66 ms 23632 KB Output is correct
34 Correct 54 ms 21132 KB Output is correct
35 Correct 58 ms 21096 KB Output is correct
36 Correct 55 ms 21068 KB Output is correct
37 Correct 208 ms 42012 KB Output is correct
38 Runtime error 87 ms 50632 KB Execution killed with signal 11
39 Runtime error 86 ms 48548 KB Execution killed with signal 11
40 Runtime error 93 ms 51044 KB Execution killed with signal 11
41 Correct 62 ms 23620 KB Output is correct
42 Correct 53 ms 21092 KB Output is correct
43 Correct 54 ms 21072 KB Output is correct
44 Correct 52 ms 20928 KB Output is correct
45 Correct 150 ms 38828 KB Output is correct
46 Runtime error 91 ms 49812 KB Execution killed with signal 11
47 Runtime error 92 ms 51160 KB Execution killed with signal 11
48 Runtime error 89 ms 52964 KB Execution killed with signal 11
49 Correct 66 ms 23232 KB Output is correct
50 Correct 55 ms 21176 KB Output is correct
51 Correct 54 ms 21156 KB Output is correct
52 Correct 53 ms 21008 KB Output is correct
53 Correct 179 ms 38220 KB Output is correct
54 Runtime error 85 ms 49816 KB Execution killed with signal 11