oj.uz

Submission #107751

# Submission time Handle Problem Language Result Execution time Memory
107751 2019-04-25T15:50:09 Z patrikpavic2 Senior Postmen (BOI14_postmen) C++17
0 / 100
 39 ms 17632 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef vector < int > vi;

const int N = 5e5 + 5;

int bio[N], n, m, nod[N],ind[N], rek[N], cur;
vector < pii > v[N];
int tura[N], st[N], tr, ss, v1[N], v2[N], deg[N];


inline bool is( const char &c ) { return c >= '0' && c <= '9'; }

inline int read_int( ) {
    int num;
    char c;
    while( !is( c = getchar_unlocked( ) ) );
    num = c - '0';
    while( is( c = getchar_unlocked( ) ) ) num = num * 10 + c - '0';
    return num;
}

inline void euler(){
    rek[cur++] = 1;
    for(;cur;){
        int x = rek[cur - 1];
        for(;ind[x] < v[x].size() && bio[v[x][ind[x]].Y];++ind[x]);
        if(ind[x] == v[x].size()) --cur, tura[tr++] = x;
        for(;ind[x] < v[x].size();++ind[x]){
            if(bio[v[x][ind[x]].Y]) continue;
            bio[v[x][ind[x]].Y] = 1;
            int nxt = v[x][ind[x]].X;
            rek[cur++] = nxt;
            break;
        }

    }
}

inline void rastavi(){
    memset(bio, 0, sizeof(bio));
    for(int i = 0;i < tr;++i){
        if(bio[tura[i]]){
            while(st[ss - 1] != tura[i]){
                printf("%d ", st[ss - 1]);
                bio[st[ss - 1]]--;
                --ss;
            }
            --ss;
            --bio[tura[i]];
            printf("%d\n", tura[i]);
        }
        st[ss++] = tura[i];
        ++bio[tura[i]];
    }
}

int main(){
    n = read_int(); m = read_int();
    for(int i = 0;i < m;++i){
        v1[i] = read_int();
        v2[i] = read_int();
        deg[v1[i]]++, deg[v2[i]]++;
    }
    for(int i = 1;i <= n;i++){
        v[i].resize(deg[i] + 1);
        deg[i] = 0;
    }
    for(int i = 0;i < m;i++){
        v[v1[i]][deg[v1[i]]++].X = v2[i];
        v[v1[i]][deg[v1[i]] - 1].Y = i;
        v[v2[i]][deg[v2[i]]++].X = v1[i];
        v[v2[i]][deg[v2[i]] - 1].Y = i;
    }
    euler();
    rastavi();
    return 0;
}

Compilation message

postmen.cpp: In function 'void euler()':
postmen.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;ind[x] < v[x].size() && bio[v[x][ind[x]].Y];++ind[x]);
              ~~~~~~~^~~~~~~~~~~~~
postmen.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ind[x] == v[x].size()) --cur, tura[tr++] = x;
            ~~~~~~~^~~~~~~~~~~~~~
postmen.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;ind[x] < v[x].size();++ind[x]){
              ~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14080 KB Output is correct
2 Correct 13 ms 14080 KB Output is correct
3 Correct 15 ms 14080 KB Output is correct
4 Correct 17 ms 14208 KB Output is correct
5 Correct 16 ms 14080 KB Output is correct
6 Correct 14 ms 14208 KB Output is correct
7 Correct 16 ms 14600 KB Output is correct
8 Correct 14 ms 14208 KB Output is correct
9 Correct 35 ms 17528 KB Output is correct
10 Incorrect 15 ms 14208 KB Edge does not exist or used 757, 1097
11 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14080 KB Output is correct
2 Correct 16 ms 14080 KB Output is correct
3 Correct 15 ms 14080 KB Output is correct
4 Correct 13 ms 14208 KB Output is correct
5 Correct 13 ms 14080 KB Output is correct
6 Correct 13 ms 14208 KB Output is correct
7 Correct 17 ms 14568 KB Output is correct
8 Correct 13 ms 14208 KB Output is correct
9 Correct 39 ms 17588 KB Output is correct
10 Incorrect 14 ms 14208 KB Edge does not exist or used 757, 1097
11 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14080 KB Output is correct
2 Correct 14 ms 14020 KB Output is correct
3 Correct 14 ms 14080 KB Output is correct
4 Correct 13 ms 14208 KB Output is correct
5 Correct 13 ms 14080 KB Output is correct
6 Correct 15 ms 14208 KB Output is correct
7 Correct 37 ms 14592 KB Output is correct
8 Correct 16 ms 14208 KB Output is correct
9 Correct 35 ms 17632 KB Output is correct
10 Incorrect 13 ms 14208 KB Edge does not exist or used 757, 1097
11 Halted 0 ms 0 KB -