oj.uz

Submission #129762

# Submission time Handle Problem Language Result Execution time Memory
129762 2019-07-13T07:32:28 Z Abelyan Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 49940 KB 
#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

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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 23 ms 24064 KB Output is correct
5 Correct 17 ms 23936 KB Output is correct
6 Correct 0 ms 24064 KB Output is correct
7 Correct 23 ms 24576 KB Output is correct
8 Correct 20 ms 23984 KB Output is correct
9 Correct 45 ms 27568 KB Output is correct
10 Correct 19 ms 23936 KB Output is correct
11 Correct 24 ms 24012 KB Output is correct
12 Correct 50 ms 27892 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 19 ms 23784 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 21 ms 23936 KB Output is correct
6 Correct 23 ms 24040 KB Output is correct
7 Correct 22 ms 24576 KB Output is correct
8 Correct 18 ms 23936 KB Output is correct
9 Correct 50 ms 27488 KB Output is correct
10 Correct 29 ms 24116 KB Output is correct
11 Correct 30 ms 23936 KB Output is correct
12 Correct 48 ms 27892 KB Output is correct
13 Correct 84 ms 29040 KB Output is correct
14 Correct 88 ms 28748 KB Output is correct
15 Correct 78 ms 28948 KB Output is correct
16 Correct 81 ms 29128 KB Output is correct
17 Correct 83 ms 28784 KB Output is correct
18 Correct 80 ms 29064 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 24 ms 23780 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 24 ms 24064 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 19 ms 24120 KB Output is correct
7 Correct 21 ms 24552 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 46 ms 27560 KB Output is correct
10 Correct 21 ms 24064 KB Output is correct
11 Correct 22 ms 24012 KB Output is correct
12 Correct 55 ms 27924 KB Output is correct
13 Correct 82 ms 29016 KB Output is correct
14 Correct 83 ms 28724 KB Output is correct
15 Correct 67 ms 28908 KB Output is correct
16 Correct 85 ms 29124 KB Output is correct
17 Correct 85 ms 28788 KB Output is correct
18 Correct 81 ms 29104 KB Output is correct
19 Correct 492 ms 49844 KB Output is correct
20 Correct 469 ms 48716 KB Output is correct
21 Correct 410 ms 49728 KB Output is correct
22 Correct 480 ms 49940 KB Output is correct
23 Correct 155 ms 41260 KB Output is correct
24 Execution timed out 546 ms 49284 KB Time limit exceeded
25 Halted 0 ms 0 KB -