oj.uz

Submission #977629

# Submission time Handle Problem Language Result Execution time Memory
977629 2024-05-08T07:52:51 Z Ning07 Swapping Cities (APIO20_swap) C++17
17 / 100
 2000 ms 14436 KB 
#include "swap.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;

#define L(i, j, k) for (int i = (j); i <= k; i++) 
#define R(i, j, k) for (int i = (j); i >= k; i--) 

const int nax = 100050;

int N, M;
vector<pair<int, int>> G[nax], edges; 

void init(int _N, int _M, std::vector<int> _U, std::vector<int> _V, std::vector<int> _W) {
   N = _N; M = _M;
   L(i, 0, M - 1){
      G[_U[i]].push_back(make_pair(_V[i], i));
      G[_V[i]].push_back(make_pair(_U[i], i));
      edges.push_back(make_pair(_W[i], i));
   }
   sort(edges.begin(), edges.end());
}

int getMinimumFuelCapacity(int X, int Y) {
   // notice that either we have a node with degree >= 3
   // or that we have a cycle
   // since the answer is the maximum, why not consider adding the edge one by one?

   vector<bool> ban(M, true), vis(N);
   function<void(int, int)> dfs = [&](int u, int f) {
      vis[u] = true;
      for (auto & v : G[u]) {
         if (ban[v.second]) continue;
         if (v.first == f) continue;
         if (vis[v.first]) continue;
         dfs(v.first, f);
      }
   };
   function<bool(int, int)> cycle = [&](int u, int f) {
      vis[u] = true;
      for (auto & v : G[u]) {
         if (ban[v.second]) continue;
         if (v.first == f) continue;

         if (vis[v.first]) return true;
         if (cycle(v.first, u)) return true;
      }
      return false;
   };
   function<bool()> degree = [&]() {
      for (int i = 0; i < N; i++) {
         int deg = 0;
         if (vis[i] == true) {
            for (auto & v : G[i]) {
               deg += ban[v.second] == false;
            }
         }
         if (deg >= 3) 
            return true;
      }
      return false;
   };
   for (int i = 0; i < M; i++) {
      int w = edges[i].first;
      int id = edges[i].second;
      ban[id] = false;
      vis = vector<bool>(N);
      dfs(X, -1);
      if (vis[Y] == false) continue;
      vis = vector<bool>(N);
      if (cycle(X, -1) || degree()) {
         return w;
      }
   }
   return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 15 ms 2904 KB Output is correct
9 Correct 134 ms 12836 KB Output is correct
10 Correct 376 ms 14356 KB Output is correct
11 Correct 529 ms 14424 KB Output is correct
12 Correct 554 ms 14436 KB Output is correct
13 Execution timed out 2033 ms 9452 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Execution timed out 2037 ms 10732 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 15 ms 2904 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 3 ms 2652 KB Output is correct
15 Correct 2 ms 2652 KB Output is correct
16 Correct 3 ms 2652 KB Output is correct
17 Correct 9 ms 2908 KB Output is correct
18 Correct 3 ms 2676 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 4 ms 2868 KB Output is correct
22 Correct 4 ms 2652 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 3 ms 2908 KB Output is correct
25 Correct 5 ms 2908 KB Output is correct
26 Correct 3 ms 2904 KB Output is correct
27 Correct 8 ms 2652 KB Output is correct
28 Correct 2 ms 2932 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 15 ms 2904 KB Output is correct
10 Correct 134 ms 12836 KB Output is correct
11 Correct 376 ms 14356 KB Output is correct
12 Correct 529 ms 14424 KB Output is correct
13 Correct 554 ms 14436 KB Output is correct
14 Execution timed out 2033 ms 9452 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 15 ms 2904 KB Output is correct
9 Correct 134 ms 12836 KB Output is correct
10 Correct 376 ms 14356 KB Output is correct
11 Correct 529 ms 14424 KB Output is correct
12 Correct 554 ms 14436 KB Output is correct
13 Execution timed out 2033 ms 9452 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 15 ms 2904 KB Output is correct
10 Correct 134 ms 12836 KB Output is correct
11 Correct 376 ms 14356 KB Output is correct
12 Correct 529 ms 14424 KB Output is correct
13 Correct 554 ms 14436 KB Output is correct
14 Execution timed out 2033 ms 9452 KB Time limit exceeded
15 Halted 0 ms 0 KB -