oj.uz

Submission #961025

# Submission time Handle Problem Language Result Execution time Memory
961025 2024-04-11T12:07:33 Z noyancanturk Senior Postmen (BOI14_postmen) C++17
55 / 100
 318 ms 23008 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=4e5+100;
const int mod=998244353;
//const int mod=(1ll<<61)-1;
 
using pii=pair<int,int>;

vector<pii>v[lim];
bool vis[lim];
vector<int>path;

void dfs(int node){
    while(v[node].size()){
        pii now=v[node].back();
        v[node].pop_back();
        if(vis[now.second])continue;
        vis[now.second]=1;
        dfs(now.first);
    }
    path.pb(node);
}

inline void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        v[x].pb({y,i});
        v[y].pb({x,i});
    }
    dfs(1);
    vector<int>cur;
    bool seen[n+1];
    memset(seen,0,sizeof(seen));
    for(int j:path){
        cerr<<j<<" ";
        if(seen[j]){
            cout<<j<<" ";
            while(cur.back()!=j){
                cout<<cur.back()<<" ";
                seen[cur.back()]=0;
                cur.pop_back();
            } 
            cout<<"\n";
        }else{
            cur.push_back(j);
            seen[j]=1;
        }
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9908 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 15 ms 10588 KB Output is correct
5 Correct 6 ms 10076 KB Output is correct
6 Correct 14 ms 10656 KB Output is correct
7 Correct 49 ms 12124 KB Output is correct
8 Correct 8 ms 10332 KB Output is correct
9 Correct 242 ms 20528 KB Output is correct
10 Correct 16 ms 10332 KB Output is correct
11 Correct 10 ms 10332 KB Output is correct
12 Correct 247 ms 20920 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9916 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 11 ms 10332 KB Output is correct
5 Correct 6 ms 10076 KB Output is correct
6 Correct 15 ms 10648 KB Output is correct
7 Correct 41 ms 12056 KB Output is correct
8 Correct 8 ms 10584 KB Output is correct
9 Correct 244 ms 20372 KB Output is correct
10 Correct 12 ms 10328 KB Output is correct
11 Correct 10 ms 10332 KB Output is correct
12 Correct 248 ms 21016 KB Output is correct
13 Correct 271 ms 22868 KB Output is correct
14 Correct 275 ms 19956 KB Output is correct
15 Correct 302 ms 22176 KB Output is correct
16 Correct 264 ms 22912 KB Output is correct
17 Correct 292 ms 17548 KB Output is correct
18 Correct 288 ms 20680 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 11 ms 10444 KB Output is correct
5 Correct 6 ms 10076 KB Output is correct
6 Correct 14 ms 10584 KB Output is correct
7 Correct 40 ms 11864 KB Output is correct
8 Correct 8 ms 10332 KB Output is correct
9 Correct 257 ms 20672 KB Output is correct
10 Correct 11 ms 10328 KB Output is correct
11 Correct 11 ms 10384 KB Output is correct
12 Correct 296 ms 20932 KB Output is correct
13 Correct 257 ms 22896 KB Output is correct
14 Correct 318 ms 19908 KB Output is correct
15 Correct 292 ms 22140 KB Output is correct
16 Correct 274 ms 23008 KB Output is correct
17 Correct 287 ms 17420 KB Output is correct
18 Correct 293 ms 20672 KB Output is correct
19 Runtime error 11 ms 20012 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -