oj.uz

Submission #465798

# Submission time Handle Problem Language Result Execution time Memory
465798 2021-08-16T18:55:37 Z AmirElarbi Senior Postmen (BOI14_postmen) C++14
38 / 100
 500 ms 15940 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define fi first
#define se second
#define INF 1e7
#define unsigned u
#define eps 1e-18
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);
#define MAX_A 100005
#define V 450
#define re register
#define maxi(a,b) ((a) > (b) ? (a) : (b))
using namespace std;
vii adj[100005];
bool vis[100005];
bool tv[100005];
int n,m,used;
bool dfs(int u, int p, int start){
    //cout << u << " " << start << " " << used << endl;
    tv[u] = 1;
    for(auto x : adj[u])
    {
        
        if(x.fi == p)
            continue;
        if(vis[x.se])
            continue;
        if(x.fi == start)
        {
            vis[x.se] = true;
            used++;
            tv[u] = 0;
            return true;
        }
        if(tv[x.fi])
            continue;
        vis[x.se] = true;
        used++;
        if(dfs(x.fi,u,start)){
            cout << x.fi << " ";
            tv[u] = 0;
            return true;
        }
        vis[x.se] = 0;
        used--;
    }
    return false;
}
int main(){
    optimise;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int a,b;
        cin >> a >>b;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
    }
    int d = 1;
    while (used != m)
    {
        for (int i = d; i <= n; ++i)
        { 
            if(dfs(i,-1,i)){
                cout << i;
                break;
            }  else 
                d++;
        }
        memset(tv, 0, sizeof tv);
        cout << endl;
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 10 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 10 ms 3276 KB Output is correct
8 Correct 3 ms 3020 KB Output is correct
9 Correct 82 ms 5216 KB Output is correct
10 Correct 9 ms 2856 KB Output is correct
11 Correct 6 ms 2892 KB Output is correct
12 Correct 67 ms 5668 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 9 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 10 ms 3276 KB Output is correct
8 Correct 3 ms 3020 KB Output is correct
9 Correct 81 ms 5228 KB Output is correct
10 Correct 8 ms 2764 KB Output is correct
11 Correct 6 ms 2892 KB Output is correct
12 Correct 59 ms 5696 KB Output is correct
13 Correct 63 ms 15864 KB Output is correct
14 Correct 56 ms 11008 KB Output is correct
15 Execution timed out 1088 ms 6064 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 9 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 10 ms 3276 KB Output is correct
8 Correct 3 ms 3020 KB Output is correct
9 Correct 81 ms 5168 KB Output is correct
10 Correct 8 ms 2860 KB Output is correct
11 Correct 6 ms 2892 KB Output is correct
12 Correct 59 ms 5692 KB Output is correct
13 Correct 59 ms 15940 KB Output is correct
14 Correct 58 ms 10964 KB Output is correct
15 Execution timed out 1092 ms 5972 KB Time limit exceeded
16 Halted 0 ms 0 KB -