Submission #107745

#	Time	Username	Problem	Language	Result	Execution time	Memory
107745		patrikpavic2	Senior Postmen (BOI14_postmen)	C++17	100 / 100	428 ms	40848 KiB

postmen

#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;

inline bool is( 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;
}

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;
        }

    }
}

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++){
        int x = read_int();
        int y = read_int();
        v[x].PB({y, i});
        v[y].PB({x, i});
    }
    euler();
    rastavi();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45