oj.uz

Submission #548731

# Submission time Handle Problem Language Result Execution time Memory
548731 2022-04-14T10:57:06 Z Amylopectin Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 94488 KB 
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;
const int mxn = 5e5 + 10;
struct we
{
    int to,nnu;
};
vector<int> ans[mxn] = {};
vector<struct we> pa[mxn] = {};
int pau[mxn] = {},nu[mxn] = {},ctr = -1,ncy = 0;
int re(int cn,int be)
{
    int i,j,fn,cnu;
    nu[cn] = 1;
    for(i=0; i<pa[cn].size(); i++)
    {
        fn = pa[cn][i].to;
        cnu = pa[cn][i].nnu;
        if(fn == be || pau[cnu] == 1)
            continue;
        if(nu[fn] == 1)
        {
            ctr = fn;
            ans[ncy].push_back(cn);
            nu[cn] = 0;
            pau[cnu] = 1;
            return 0;
        }
        re(fn,cn);
        if(ctr != -1)
        {
            ans[ncy].push_back(cn);
            pau[cnu] = 1;
            if(cn != ctr)
            {
                nu[cn] = 0;
                return 0;
            }
            ncy ++;
            ctr = -1;
        }
    }
    nu[cn] = 0;
    return 0;
}
int main()
{
    int i,j,n,m,cn,cm,fn,fm;
    scanf("%d %d",&n,&m);
    for(i=0; i<m; i++)
    {
        scanf("%d %d",&cn,&cm);
        pa[cn].push_back({cm,i});
        pa[cm].push_back({cn,i});
    }
    for(i=1; i<=n; i++)
    {
        re(i,-1);
    }
    for(i=0; i<ncy; i++)
    {
        for(j=0; j<ans[i].size(); j++)
        {
            printf("%d ",ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Compilation message

postmen.cpp: In function 'int re(int, int)':
postmen.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(i=0; i<pa[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~
postmen.cpp:16:11: warning: unused variable 'j' [-Wunused-variable]
   16 |     int i,j,fn,cnu;
      |           ^
postmen.cpp: In function 'int main()':
postmen.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(j=0; j<ans[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
postmen.cpp:51:23: warning: unused variable 'fn' [-Wunused-variable]
   51 |     int i,j,n,m,cn,cm,fn,fm;
      |                       ^~
postmen.cpp:51:26: warning: unused variable 'fm' [-Wunused-variable]
   51 |     int i,j,n,m,cn,cm,fn,fm;
      |                          ^~
postmen.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
postmen.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23788 KB Output is correct
2 Correct 16 ms 23680 KB Output is correct
3 Correct 14 ms 23768 KB Output is correct
4 Correct 15 ms 23932 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 14 ms 23892 KB Output is correct
7 Correct 19 ms 24444 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 129 ms 27704 KB Output is correct
10 Correct 13 ms 23864 KB Output is correct
11 Correct 13 ms 23892 KB Output is correct
12 Correct 61 ms 28220 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 16 ms 23792 KB Output is correct
3 Correct 18 ms 23792 KB Output is correct
4 Correct 15 ms 23864 KB Output is correct
5 Correct 15 ms 23764 KB Output is correct
6 Correct 16 ms 23956 KB Output is correct
7 Correct 25 ms 24520 KB Output is correct
8 Correct 19 ms 24020 KB Output is correct
9 Correct 91 ms 27636 KB Output is correct
10 Correct 15 ms 23892 KB Output is correct
11 Correct 18 ms 23892 KB Output is correct
12 Correct 70 ms 28112 KB Output is correct
13 Correct 78 ms 37716 KB Output is correct
14 Correct 77 ms 29680 KB Output is correct
15 Correct 61 ms 29376 KB Output is correct
16 Correct 74 ms 37696 KB Output is correct
17 Correct 82 ms 29924 KB Output is correct
18 Correct 84 ms 31716 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23796 KB Output is correct
2 Correct 13 ms 23796 KB Output is correct
3 Correct 13 ms 23804 KB Output is correct
4 Correct 15 ms 23964 KB Output is correct
5 Correct 13 ms 23752 KB Output is correct
6 Correct 14 ms 23892 KB Output is correct
7 Correct 19 ms 24456 KB Output is correct
8 Correct 13 ms 24068 KB Output is correct
9 Correct 119 ms 27644 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 16 ms 23976 KB Output is correct
12 Correct 62 ms 28236 KB Output is correct
13 Correct 110 ms 37776 KB Output is correct
14 Correct 70 ms 29624 KB Output is correct
15 Correct 76 ms 29368 KB Output is correct
16 Correct 91 ms 37752 KB Output is correct
17 Correct 69 ms 29936 KB Output is correct
18 Correct 88 ms 31780 KB Output is correct
19 Execution timed out 577 ms 94488 KB Time limit exceeded
20 Halted 0 ms 0 KB -