Submission #129762

#	Time	Username	Problem	Language	Result	Execution time	Memory
129762		Abelyan	Senior Postmen (BOI14_postmen)	C++17	55 / 100	546 ms	49940 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
 
 
 
class fastIO{
private:
    long long P10[19];
public:
    fastIO(){
        P10[0]=1;
        for (int i=1;i<=18;++i){
            P10[i]=P10[i-1]*10;
        }
    }
    long long read() {
        char ch=getchar();
        long long mul=1;
        if (ch=='-'){
            mul=-1;
            ch=getchar();
        }
        long long pat=0;
        while(ch==10 || ch==32)ch=getchar();
        while(ch>='0' && ch<='9'){
            pat=pat*10ll+(long long)(ch-'0');
            //cout<<ch<<endl;
            ch=getchar();
        }
        return pat*mul;
    }
    char readCh(){
        char ch=getchar();
        while(ch==10 || ch==32)ch=getchar();
        return ch;
    }
    void readStr(string &s){
        s="";
        char ch=getchar();
        while(ch==10 || ch==32)ch=getchar();
        while(ch!=10 && ch!=32){
            s+=ch;
            ch=getchar();
        }
 
    }
    void writeInt(int k,bool aft=false){
        if (k==0){
            putchar('0');
            putchar(32);
            return;
        }
        if (k<0){
            k=-k;
            putchar('-');
        }
        bool zro=false;
        for (int i=9;i>=0;--i){
            int tv=k/P10[i];
            k%=P10[i];
            if (tv==0 && !zro)continue;
            zro=true;
            putchar(tv+'0');
        }
        if (!aft) putchar(32);
    }
    void writeLL(long long k,bool aft=false){
        if (k==0){
            putchar('0');
            putchar(32);
            return;
        }
        if (k<0){
            k=-k;
            putchar('-');
        }
        bool zro=false;
        for (int i=18;i>=0;--i){
            int tv=k/P10[i];
            k%=P10[i];
            if (tv==0 && !zro)continue;
            zro=true;
            putchar(tv+'0');
        }
        if (!aft) putchar(32);
    }
    void writeStr(string &s,bool aft=false){
        int sz=s.length();
        for (int i=0;i<sz;++i){
            putchar(s[i]);
        }
        if (!aft) putchar(32);
    }
    void writechar(char k){
        putchar(k);
    }
    void space(){
        putchar(32);
    }
    void nwLn(){
        putchar(10);
    }
} io;
 
const int N=5e5+10;
const ll MOD=1e9+7;
 
vector<pir> g[N];
vector<int> ans[N],eu;
bool fr[N],col[N];
 
int main(){
    fastio;
    srng;
    int n=io.read(),m=io.read();
    //cin>>n>>m;
    FOR(i,m){
        int a=io.read(),b=io.read();
        //cin>>a>>b;
        g[a].ad({b,i});
        g[b].ad({a,i});
    }
    vector<int> st;
    st.ad(1);
    while(st.size()){
        int v=st.back();
        //st.pop_back();
        //cout<<v<<" "<<g[v].size()<<endl;
        while(g[v].size() && col[g[v].back().sc])g[v].pop_back();
        if (!g[v].size()){
            st.pop_back();
            eu.ad(v);
            continue;
        }
        int to=g[v].back().fr,kox=g[v].back().sc;
        col[kox]=true;
        g[v].pop_back();
        st.ad(to);
    }
    int cnt=0;
    //cout<<eu.size()<<endl;
    FOR(i,eu.size()){
        //cout<<eu[i]<<" ";
        if (fr[eu[i]]){
            ans[cnt].ad(eu[i]);
            while(st.size() && st.back()!=eu[i]){
                fr[st.back()]=false;
                ans[cnt].ad(st.back());
                st.pop_back();
            }
            cnt++;
        }
        else{
            fr[eu[i]]=true;
            st.ad(eu[i]);
        }
    }
    //cout<<endl;
    FOR(i,cnt){
        trav(tv,ans[i])io.writeInt(tv);
        io.nwLn();
    }
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
postmen.cpp:164:5: note: in expansion of macro 'FOR'
     FOR(i,eu.size()){
     ^~~
postmen.cpp:137:9: warning: unused variable 'n' [-Wunused-variable]
     int n=io.read(),m=io.read();
         ^

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