Submission #547998

#	Time	Username	Problem	Language	Result	Execution time	Memory
547998		Amylopectin	Pipes (BOI13_pipes)	C++14	74.07 / 100	241 ms	47948 KiB

pipes

#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 (stderr)

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 / 30
• Subtask 2: 44.074074074074076 / 70