Submission #107748

#	Time	Username	Problem	Language	Result	Execution time	Memory
107748		patrikpavic2	Senior Postmen (BOI14_postmen)	C++17	100 / 100	439 ms	40964 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( 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){
        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