oj.uz

Submission #548331

# Submission time Handle Problem Language Result Execution time Memory
548331 2022-04-13T04:17:07 Z Amylopectin Pipes (BOI13_pipes) C++14
74.0741 / 100
 221 ms 54696 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()
{
//    freopen("pipes.g12-9.in","r",stdin);
    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:72:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(i=0; i<pa[cn].size(); i++)
      |                      ~^~~~~~~~~~~~~~
pipes.cpp:114:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for(i=0; i<pa[cn].size(); i++)
      |                      ~^~~~~~~~~~~~~~
pipes.cpp:37:32: warning: unused variable 'fm' [-Wunused-variable]
   37 |     long long i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
      |                                ^~
pipes.cpp:37:47: warning: unused variable 'of' [-Wunused-variable]
   37 |     long long i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
      |                                               ^~
pipes.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
pipes.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld",&nva[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%lld %lld",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
pipes.cpp:152:11: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  152 |         re(st,-1,0);
      |         ~~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14400 KB Output is correct
2 Correct 10 ms 14404 KB Output is correct
3 Correct 11 ms 14548 KB Output is correct
4 Correct 87 ms 25780 KB Output is correct
5 Correct 7 ms 14384 KB Output is correct
6 Correct 8 ms 14384 KB Output is correct
7 Correct 8 ms 14364 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14548 KB Output is correct
11 Correct 9 ms 14468 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 61 ms 23448 KB Output is correct
14 Correct 89 ms 25160 KB Output is correct
15 Correct 83 ms 25932 KB Output is correct
16 Correct 69 ms 24140 KB Output is correct
17 Correct 91 ms 25780 KB Output is correct
18 Correct 107 ms 25924 KB Output is correct
19 Correct 95 ms 25476 KB Output is correct
20 Correct 8 ms 14400 KB Output is correct
21 Correct 8 ms 14412 KB Output is correct
22 Correct 83 ms 25808 KB Output is correct
23 Correct 62 ms 23500 KB Output is correct
24 Correct 89 ms 25868 KB Output is correct
25 Correct 84 ms 23916 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 29028 KB Execution killed with signal 11
2 Runtime error 20 ms 29300 KB Execution killed with signal 11
3 Correct 72 ms 24708 KB Output is correct
4 Correct 67 ms 22736 KB Output is correct
5 Correct 66 ms 22460 KB Output is correct
6 Correct 216 ms 43600 KB Output is correct
7 Runtime error 20 ms 29016 KB Execution killed with signal 11
8 Runtime error 20 ms 29056 KB Execution killed with signal 11
9 Correct 8 ms 14336 KB Output is correct
10 Correct 8 ms 14400 KB Output is correct
11 Correct 9 ms 14400 KB Output is correct
12 Correct 10 ms 14400 KB Output is correct
13 Correct 8 ms 14440 KB Output is correct
14 Runtime error 19 ms 29012 KB Execution killed with signal 11
15 Runtime error 20 ms 29252 KB Execution killed with signal 11
16 Runtime error 22 ms 29232 KB Execution killed with signal 11
17 Correct 9 ms 14536 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14404 KB Output is correct
20 Correct 8 ms 14408 KB Output is correct
21 Correct 9 ms 14720 KB Output is correct
22 Runtime error 26 ms 29260 KB Execution killed with signal 11
23 Runtime error 88 ms 48876 KB Execution killed with signal 11
24 Runtime error 89 ms 52812 KB Execution killed with signal 11
25 Correct 61 ms 24652 KB Output is correct
26 Correct 62 ms 22752 KB Output is correct
27 Correct 79 ms 22620 KB Output is correct
28 Correct 65 ms 22988 KB Output is correct
29 Correct 174 ms 38204 KB Output is correct
30 Runtime error 88 ms 51592 KB Execution killed with signal 11
31 Runtime error 105 ms 54696 KB Execution killed with signal 11
32 Runtime error 83 ms 50680 KB Execution killed with signal 11
33 Correct 67 ms 25332 KB Output is correct
34 Correct 60 ms 22672 KB Output is correct
35 Correct 61 ms 22644 KB Output is correct
36 Correct 57 ms 22756 KB Output is correct
37 Correct 221 ms 43540 KB Output is correct
38 Runtime error 88 ms 52172 KB Execution killed with signal 11
39 Runtime error 84 ms 50144 KB Execution killed with signal 11
40 Runtime error 89 ms 52584 KB Execution killed with signal 11
41 Correct 60 ms 25156 KB Output is correct
42 Correct 56 ms 22684 KB Output is correct
43 Correct 57 ms 22608 KB Output is correct
44 Correct 52 ms 22400 KB Output is correct
45 Correct 157 ms 40484 KB Output is correct
46 Runtime error 85 ms 51428 KB Execution killed with signal 11
47 Runtime error 86 ms 52720 KB Execution killed with signal 11
48 Runtime error 88 ms 54600 KB Execution killed with signal 11
49 Correct 64 ms 24776 KB Output is correct
50 Correct 54 ms 22696 KB Output is correct
51 Correct 56 ms 22848 KB Output is correct
52 Correct 53 ms 22468 KB Output is correct
53 Correct 169 ms 39932 KB Output is correct
54 Runtime error 102 ms 51220 KB Execution killed with signal 11