oj.uz

Submission #1075001

# Submission time Handle Problem Language Result Execution time Memory
1075001 2024-08-25T17:28:06 Z Osplei Senior Postmen (BOI14_postmen) C++11
38 / 100
 500 ms 26472 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int> ii;
typedef int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii; 
typedef vector<vii> wgraf;
typedef pair<int,ii> edge;
typedef vector <ll> vl;
typedef pair <ll, ll> LL;
typedef vector <LL> vll;
 
#define UNVISITED 0
#define VISITED 1
#define pb push_back
#define F first
#define S second
 
ll n, m, u, v, visto[500005], cone[500005];
vll grafo[500005];
bool vale = false, puede[500005];

void dfs(ll origen, ll nodo, ll aux) {
  
  for (auto i : grafo[nodo]) {

    if (puede[i.S] == true && visto[i.F] != aux) {
    
      puede[i.S] = false;
      visto[i.F] = aux;
      
      if (i.F == origen) {
      
        cout << nodo << " ";
        vale = true;

        return;
      
      }

      dfs(origen, i.F, aux);

      if (vale == true) {
      
        cout << nodo << " ";
 
        return;
      
      }

      puede[i.S] = true;
    
    }
    
  }

}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin >> n >> m;

  for (ll i = 0; i < n; i++) visto[i] = 0;

  for (ll i = 0; i < m; i++){
    cin >> u >> v;

    grafo[u].pb({v, i});
    grafo[v].pb({u, i});

    puede[i] = true;
    cone[i] = u;
  }

  ll cnt = 0;

  for (ll i = 0; i < m; i++) {
    if (puede[i] == true) {
      vale = false;
      cnt++;
      dfs(cone[i], cone[i], cnt);
      cout << "\n";
    }
  }
  
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 5 ms 14896 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 9 ms 15336 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Correct 54 ms 17316 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 32 ms 17572 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 5 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 7 ms 15308 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 51 ms 17272 KB Output is correct
10 Correct 4 ms 14680 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 32 ms 17776 KB Output is correct
13 Correct 34 ms 26472 KB Output is correct
14 Correct 52 ms 22224 KB Output is correct
15 Execution timed out 1078 ms 17832 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 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 5 ms 14684 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 7 ms 15196 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 56 ms 17236 KB Output is correct
10 Correct 4 ms 14684 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 32 ms 17764 KB Output is correct
13 Correct 33 ms 26284 KB Output is correct
14 Correct 54 ms 22096 KB Output is correct
15 Execution timed out 1045 ms 17876 KB Time limit exceeded
16 Halted 0 ms 0 KB -