oj.uz

Submission #465757

# Submission time Handle Problem Language Result Execution time Memory
465757 2021-08-16T18:03:36 Z AmirElarbi Senior Postmen (BOI14_postmen) C++14
38 / 100
 106 ms 10988 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[2005];
bool vis[100005];
bool tv[2005];
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++;
            if(used == m)
                return true;
            for (int i = 1; i <= n; ++i)
            {
                //cout << i << endl;
                memset(tv, 0, sizeof tv);
                
                if(dfs(i,-1,i)){
                    cout  << i << endl;
                    return true;
                }
            }
            vis[x.se] = 0;
            used--;
            return false;
        }
        if(tv[x.fi])
            continue;
        vis[x.se] = true;
        used++;
        if(dfs(x.fi,u,start)){
            cout << x.fi << " ";
            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});
    }
    for (int i = 1; i <= n; ++i)
    {
        used = 0;
        if(dfs(i,-1,i)){
            cout << i;
            return 0;
        }
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 9 ms 1996 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 87 ms 10592 KB Output is correct
10 Correct 29 ms 648 KB Output is correct
11 Correct 23 ms 588 KB Output is correct
12 Correct 85 ms 10988 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 9 ms 1996 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 85 ms 10608 KB Output is correct
10 Correct 29 ms 644 KB Output is correct
11 Correct 23 ms 640 KB Output is correct
12 Correct 85 ms 10952 KB Output is correct
13 Runtime error 1 ms 460 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 9 ms 1996 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 106 ms 10596 KB Output is correct
10 Correct 29 ms 660 KB Output is correct
11 Correct 23 ms 640 KB Output is correct
12 Correct 106 ms 10876 KB Output is correct
13 Runtime error 1 ms 460 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -