Submission #107741

#	Time	Username	Problem	Language	Result	Execution time	Memory
107741		patrikpavic2	어르신 집배원 (BOI14_postmen)	C++17	55 / 100	551 ms	40952 KiB

postmen

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <stack>
#include <set>
#include <vector>
#include <iostream>
#include <queue>
#include <map>

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef set < int > si;

const int N = 5e5 + 5;
const int M = 1e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int OFF = (1 << 18);
const int LOG = 20;
const double EPS = 1e-9;
const double PI = 3.1415926535;

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

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(){
    scanf("%d%d", &n, &m);
    for(int i = 0;i < m;i++){
        int x, y; scanf("%d%d", &x, &y);
        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:43: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:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ind[x] == v[x].size()) cur--, tura[tr++] = x;
            ~~~~~~~^~~~~~~~~~~~~~
postmen.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;ind[x] < v[x].size();ind[x]++){
              ~~~~~~~^~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:77:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%d%d", &x, &y);
                   ~~~~~^~~~~~~~~~~~~~~~

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