oj.uz

Submission #548323

# Submission time Handle Problem Language Result Execution time Memory
548323 2022-04-13T04:05:02 Z Amylopectin Pipes (BOI13_pipes) C++14
74.0741 / 100
 286 ms 54864 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 14400 KB Output is correct
3 Correct 10 ms 14548 KB Output is correct
4 Correct 90 ms 25860 KB Output is correct
5 Correct 10 ms 14396 KB Output is correct
6 Correct 10 ms 14420 KB Output is correct
7 Correct 9 ms 14360 KB Output is correct
8 Correct 9 ms 14428 KB Output is correct
9 Correct 9 ms 14416 KB Output is correct
10 Correct 8 ms 14532 KB Output is correct
11 Correct 9 ms 14536 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 71 ms 23460 KB Output is correct
14 Correct 108 ms 25136 KB Output is correct
15 Correct 89 ms 25868 KB Output is correct
16 Correct 68 ms 24076 KB Output is correct
17 Correct 95 ms 25824 KB Output is correct
18 Correct 108 ms 25872 KB Output is correct
19 Correct 102 ms 25584 KB Output is correct
20 Correct 8 ms 14420 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct
22 Correct 96 ms 25804 KB Output is correct
23 Correct 87 ms 23428 KB Output is correct
24 Correct 88 ms 26044 KB Output is correct
25 Correct 73 ms 23856 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 28984 KB Execution killed with signal 11
2 Runtime error 21 ms 29200 KB Execution killed with signal 11
3 Correct 76 ms 24600 KB Output is correct
4 Correct 86 ms 22728 KB Output is correct
5 Correct 71 ms 22476 KB Output is correct
6 Correct 286 ms 48132 KB Output is correct
7 Runtime error 23 ms 29012 KB Execution killed with signal 11
8 Runtime error 23 ms 28992 KB Execution killed with signal 11
9 Correct 9 ms 14392 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 14396 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Runtime error 20 ms 29020 KB Execution killed with signal 11
15 Runtime error 23 ms 29344 KB Execution killed with signal 11
16 Runtime error 22 ms 29168 KB Execution killed with signal 11
17 Correct 9 ms 14492 KB Output is correct
18 Correct 11 ms 14404 KB Output is correct
19 Correct 9 ms 14420 KB Output is correct
20 Correct 10 ms 14416 KB Output is correct
21 Correct 10 ms 14512 KB Output is correct
22 Runtime error 20 ms 29248 KB Execution killed with signal 11
23 Runtime error 73 ms 48920 KB Execution killed with signal 11
24 Runtime error 97 ms 52812 KB Execution killed with signal 11
25 Correct 86 ms 24648 KB Output is correct
26 Correct 56 ms 22744 KB Output is correct
27 Correct 52 ms 22608 KB Output is correct
28 Correct 62 ms 23028 KB Output is correct
29 Correct 216 ms 41668 KB Output is correct
30 Runtime error 96 ms 51532 KB Execution killed with signal 11
31 Runtime error 98 ms 54864 KB Execution killed with signal 11
32 Runtime error 97 ms 50628 KB Execution killed with signal 11
33 Correct 83 ms 25220 KB Output is correct
34 Correct 60 ms 22676 KB Output is correct
35 Correct 55 ms 22744 KB Output is correct
36 Correct 56 ms 22780 KB Output is correct
37 Correct 270 ms 48140 KB Output is correct
38 Runtime error 92 ms 52268 KB Execution killed with signal 11
39 Runtime error 87 ms 50132 KB Execution killed with signal 11
40 Runtime error 109 ms 52624 KB Execution killed with signal 11
41 Correct 67 ms 25160 KB Output is correct
42 Correct 57 ms 22608 KB Output is correct
43 Correct 55 ms 22696 KB Output is correct
44 Correct 65 ms 22480 KB Output is correct
45 Correct 189 ms 44108 KB Output is correct
46 Runtime error 88 ms 51428 KB Execution killed with signal 11
47 Runtime error 97 ms 52724 KB Execution killed with signal 11
48 Runtime error 105 ms 54484 KB Execution killed with signal 11
49 Correct 75 ms 24652 KB Output is correct
50 Correct 62 ms 22860 KB Output is correct
51 Correct 59 ms 22748 KB Output is correct
52 Correct 60 ms 22492 KB Output is correct
53 Correct 203 ms 43892 KB Output is correct
54 Runtime error 90 ms 51276 KB Execution killed with signal 11