제출 #548348

#제출 시각아이디문제언어결과실행 시간메모리
548348AmylopectinPipes (BOI13_pipes)C++14
100 / 100
262 ms42696 KiB
#include <iostream> #include <stdio.h> #include <vector> #include <queue> using namespace std; const int 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 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,cou+1); } return 0; } int main() { // freopen("pipes.g07-1.in","r",stdin); // freopen("ex 1.out","a",stdout); 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,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; }

컴파일 시 표준 에러 (stderr) 메시지

pipes.cpp: In function 'long long int re(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: In function 'int main()':
pipes.cpp:74:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(i=0; i<pa[cn].size(); i++)
      |                      ~^~~~~~~~~~~~~~
pipes.cpp:116:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for(i=0; i<pa[cn].size(); i++)
      |                      ~^~~~~~~~~~~~~~
pipes.cpp:39:32: warning: unused variable 'fm' [-Wunused-variable]
   39 |     long long i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
      |                                ^~
pipes.cpp:39:47: warning: unused variable 'of' [-Wunused-variable]
   39 |     long long i,j,n,m,cn,cm,fn,fm,cou = 0,cnu,of,cyn,st,su,csu;
      |                                               ^~
pipes.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
pipes.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%lld",&nva[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%lld %lld",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
pipes.cpp:154:11: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  154 |         re(st,0);
      |         ~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...