Submission #1277906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277906		sssukhpreet2003	Senior Postmen (BOI14_postmen)	C++20	0 / 100	2 ms	500 KiB

postmen

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<ll>
#define vvll vector<ll>
#define vii vector<pii>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rev(i,a,b) for(int i=a;i>b;i--)
const int MOD=1e9+7;
const ll inf=1e18+7;

ll binaryExp(ll a,ll b){
    if(b==0) return 1;
    int temp=binaryExp(a,b/2);
    if(b%2==1) return ((temp*temp)%MOD * a) % MOD;
    else return (temp*temp) % MOD;
}

ll inv(ll a){
    return binaryExp(a,MOD-2);
}

ll nCr(ll n, ll r){
    int x=1;
    for(int i=r+1;i<=n;i++){
        x=(x*i)%MOD;
        x=(x*inv(n-i+1))%MOD;
    }
    return x;
}

template <typename T> struct segTree{
    int n;
    T ID=0;
    vector<T> st,t;
    void init(vector<T> &v){
        n=v.size();
        st.assign(4*n,ID);
        t=v;
    }
    T comb(T a,T b) {
        return a+b;
    }
    void print(){
        rep(i,0,st.size()) cout<<st[i]<<" ";
        cout<<endl;
    }
    void build(int l,int r,int root){
        if(l==r){
            st[root]=t[l];
            return;
        }
        int mid=(l+r)/2;
        build(l,mid,2*root);
        build(mid+1,r,2*root+1);
        st[root]=comb(st[2*root],st[2*root+1]);
    }
    void upd(int i,int new_val,int l, int r, int root){
        if(l==r){
            st[root]=new_val;
            return;
        }
        int mid=(l+r)/2;
        if(i>mid){
            upd(i,new_val,mid+1,r,2*root+1);
        }
        else{
            upd(i,new_val,l,mid,2*root);
        }
        st[root]=comb(st[2*root],st[2*root+1]);
    }
    T query(int ql,int qr, int l, int r, int root){
        if(ql>qr) return 0;
        if(ql==l && qr==r) return st[root];
        int mid=(l+r)/2;
        return comb(query(ql,min(qr,mid),l,mid,2*root),query(max(mid+1,ql),qr,mid+1,r,2*root+1));
    }
};

void dfs(int root, vector<int> &ans, vector<set<int>> &g, vector<vector<int>> &res,vector<bool> &exists){
    while(g[root].size()){
        int next=*g[root].begin();
        g[next].erase(root);
        g[root].erase(next);
        dfs(next,ans,g,res,exists);
    }
    if(!exists[root]) {
        exists[root]=true;
        ans.push_back(root);
    }
    else{
        vector<int> temp;
        while(ans.back()!=root){
            temp.push_back(ans.back());
            exists[ans.back()]=false;
            ans.pop_back();
        }
        temp.push_back(ans.back());
        res.push_back(temp);
    }
}

int main(){
time_t start,end;
time(&start);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
    int n,m;cin>>n>>m;
    vector<set<int>> g(n+1);
    vector<int> deg(n+1);
    vector<int> ans;
    vector<vector<int>> res;
    vector<bool> exists(n+1);
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        g[a].insert(b);
        g[b].insert(a);
        deg[a]++;
        deg[b]++;
    }
    // for(int i=0;i<n+1;i++) if(deg[i]%2) {cout<<"IMPOSSIBLE"<<endl; return 0;}
    dfs(1,ans,g,res,exists);
    // if(ans.size()!=m+1) {cout<<"IMPOSSIBLE"<<endl; return 0;}
    // for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<" ";
    // cout<<endl;

    for(int i=0;i<res.size();i++){
        for(int j=0;j<res[i].size();j++){
            cout<<res[i][j]<<" ";
        }cout<<endl;
    }
    
time(&end);
return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:118:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 | freopen("input.txt","r",stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
postmen.cpp:119:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 | freopen("output.txt","w",stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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