oj.uz

Submission #547998

# Submission time Handle Problem Language Result Execution time Memory
547998 2022-04-12T08:06:51 Z Amylopectin Pipes (BOI13_pipes) C++14
74.0741 / 100
 241 ms 47948 KB 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
const int mxn = 6e5 + 10;
struct we
{
    int to,num;
};
queue<int> qu;
vector<struct we> pa[mxn] = {};
int patva[mxn] = {},nva[mxn] = {},ind[mxn] = {},u[mxn] = {},upa[mxn] = {},sta = 0,li[mxn] = {},pnu[mxn] = {};
int re(int cn,int be,int cou)
{
    int 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()
{
    int i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
    scanf("%d %d",&n,&m);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&nva[i]);
    }
    for(j=0; j<m; j++)
    {
        scanf("%d %d",&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("%d\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("%d\n",patva[i] * 2);
        }
    }
    return 0;
}

Compilation message

pipes.cpp: In function 'int re(int, int, int)':
pipes.cpp:20:15: warning: comparison of integer expressions of different signedness: '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:11: warning: unused variable 'j' [-Wunused-variable]
   17 |     int 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: '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: '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:26: warning: unused variable 'fm' [-Wunused-variable]
   36 |     int i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
      |                          ^~
pipes.cpp:36:41: warning: unused variable 'of' [-Wunused-variable]
   36 |     int 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("%d %d",&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("%d",&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("%d %d",&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 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 10 ms 14420 KB Output is correct
4 Correct 88 ms 22272 KB Output is correct
5 Correct 10 ms 14420 KB Output is correct
6 Correct 8 ms 14400 KB Output is correct
7 Correct 8 ms 14396 KB Output is correct
8 Correct 9 ms 14420 KB Output is correct
9 Correct 8 ms 14412 KB Output is correct
10 Correct 8 ms 14496 KB Output is correct
11 Correct 8 ms 14476 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 75 ms 20596 KB Output is correct
14 Correct 79 ms 21844 KB Output is correct
15 Correct 85 ms 22352 KB Output is correct
16 Correct 75 ms 21060 KB Output is correct
17 Correct 85 ms 22240 KB Output is correct
18 Correct 80 ms 22324 KB Output is correct
19 Correct 85 ms 21604 KB Output is correct
20 Correct 10 ms 14348 KB Output is correct
21 Correct 9 ms 14444 KB Output is correct
22 Correct 100 ms 22332 KB Output is correct
23 Correct 76 ms 20644 KB Output is correct
24 Correct 92 ms 22336 KB Output is correct
25 Correct 76 ms 21008 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 29020 KB Execution killed with signal 11
2 Runtime error 27 ms 29184 KB Execution killed with signal 11
3 Correct 75 ms 21100 KB Output is correct
4 Correct 60 ms 19920 KB Output is correct
5 Correct 57 ms 20120 KB Output is correct
6 Correct 241 ms 35156 KB Output is correct
7 Runtime error 21 ms 29012 KB Execution killed with signal 11
8 Runtime error 20 ms 28992 KB Execution killed with signal 11
9 Correct 8 ms 14392 KB Output is correct
10 Correct 11 ms 14404 KB Output is correct
11 Correct 11 ms 14420 KB Output is correct
12 Correct 11 ms 14400 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Runtime error 23 ms 28988 KB Execution killed with signal 11
15 Runtime error 22 ms 29192 KB Execution killed with signal 11
16 Runtime error 22 ms 29140 KB Execution killed with signal 11
17 Correct 8 ms 14408 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14420 KB Output is correct
21 Correct 9 ms 14412 KB Output is correct
22 Runtime error 22 ms 29156 KB Execution killed with signal 11
23 Runtime error 67 ms 43296 KB Execution killed with signal 11
24 Runtime error 86 ms 45816 KB Execution killed with signal 11
25 Correct 58 ms 21128 KB Output is correct
26 Correct 56 ms 20156 KB Output is correct
27 Correct 51 ms 19780 KB Output is correct
28 Correct 53 ms 20376 KB Output is correct
29 Correct 174 ms 31428 KB Output is correct
30 Runtime error 80 ms 44304 KB Execution killed with signal 11
31 Runtime error 82 ms 47948 KB Execution killed with signal 11
32 Runtime error 81 ms 43572 KB Execution killed with signal 11
33 Correct 59 ms 21344 KB Output is correct
34 Correct 52 ms 19892 KB Output is correct
35 Correct 53 ms 19960 KB Output is correct
36 Correct 54 ms 20292 KB Output is correct
37 Correct 190 ms 35204 KB Output is correct
38 Runtime error 82 ms 44924 KB Execution killed with signal 11
39 Runtime error 83 ms 43156 KB Execution killed with signal 11
40 Runtime error 78 ms 45616 KB Execution killed with signal 11
41 Correct 57 ms 21120 KB Output is correct
42 Correct 60 ms 19868 KB Output is correct
43 Correct 52 ms 19788 KB Output is correct
44 Correct 55 ms 20300 KB Output is correct
45 Correct 147 ms 32336 KB Output is correct
46 Runtime error 83 ms 44048 KB Execution killed with signal 11
47 Runtime error 79 ms 45700 KB Execution killed with signal 11
48 Runtime error 81 ms 47784 KB Execution killed with signal 11
49 Correct 62 ms 21312 KB Output is correct
50 Correct 54 ms 20036 KB Output is correct
51 Correct 53 ms 20128 KB Output is correct
52 Correct 52 ms 19944 KB Output is correct
53 Correct 155 ms 32444 KB Output is correct
54 Runtime error 81 ms 44168 KB Execution killed with signal 11