Submission #227749

#	Time	Username	Problem	Language	Result	Execution time	Memory
227749		Shafin666	Senior Postmen (BOI14_postmen)	C++14	55 / 100	612 ms	65268 KiB

postmen

#include <bits/stdc++.h>
#define pb push_back
#define nyan "(=^･ω･^=)"
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
const int maxn = 1e6+10;
vector<int> adj[maxn], euler;
int del[maxn], l[maxn], r[maxn];
int pre[maxn], curr[maxn];
 
int main() 
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for(int i = 1; i <= m; i++) {
        scanf("%d %d", &l[i], &r[i]);
 
        adj[l[i]].pb(i);
        adj[r[i]].pb(i);
    }
    for(int i = 1; i <= n; i++) adj[i].pb(0);
 
    stack<int> s;
 
    s.push(1) ;
    while(!s.empty()) {
        int u = s.top();
        s.pop();
 
        while(curr[u] < (int) adj[u].size() - 1) {
            while(del[adj[u][curr[u]]]) curr[u]++;
            int e = adj[u][curr[u]++];
            if(e == 0) break;
 
            s.push(u);
 
            u = l[e] ^ r[e] ^ u;
            del[e] = 1;
        }
        euler.pb(u);
    }
    memset(pre, -1, sizeof pre);
 
    int j = 0;
    while(j < (int) euler.size()) {
        s.push(euler[j]);
 
        if(pre[euler[j]] != -1) {
            s.pop();
 
            while(1) {
                int here = s.top();
                printf("%d ", here);
                
                if(pre[here] == pre[euler[j]]) break;
                pre[here] = -1;
                s.pop();
            }
            printf("\n");
        }
        else pre[euler[j]] = j;
        j++;
    }
    return 0;   
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:17: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:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l[i], &r[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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