oj.uz

Submission #979696

# Submission time Handle Problem Language Result Execution time Memory
979696 2024-05-11T10:04:38 Z vjudge1 Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 53592 KB 
#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>


#include "swap.h"

#include <cassert>
#include <cstdio>


using namespace std;
vector<int> g[200005];
pair<int, int> p[200005];
map<pair<int, int>, int> mp, pos;
set<pair<int, int>> st;
int x, y, mx;
bool ok = 0;
vector<int> A, B, C;
bool us[200005];

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
      x = N;
      y = M;
      if(x - 1 != y) ok = 1;
      for(int i = 0; i < M; i++){
          int a = U[i] + 1, b = V[i] + 1, c = W[i];
          if(a != 1) ok = 1;
          mp[{a, b}] = c;
          mp[{b, a}] = c;

          pos[{a, b}] = i + 1;
          pos[{b, a}] = i + 1; 

          st.insert({c, i + 1});
          A.push_back(a);
          B.push_back(b);
          C.push_back(c);
      }
      
}
int kol = 0, kol1 = 0;
int dist[200005];
map<pair<int, int>, int> edge;
void dfs(int k){
  us[k] = 1;
  kol++;
  for(int to : g[k]){
    if(edge[{k, to}] == 0){
      edge[{k, to}]++;
      edge[{to, k}]++;
      kol1++;
    }
    if(us[to]) continue;
    dfs(to);
  }
}
int getMinimumFuelCapacity(int X, int Y) {
  if(ok){
      X++;
      Y++;
      int L = 0, R = 1e9 + 1;
      while(L + 1 < R){
        int mid = (L + R) / 2;
        kol = 0;
        for(int i = 0; i <= x; i++){
          g[i].clear();
          us[i] = 0;
        }
        for(int i = 0; i < y; i++){
            if(C[i] <= mid){
              g[A[i]].push_back(B[i]);
              g[B[i]].push_back(A[i]);
            }
        }
        int kk = 0;
        for(int i = 1; i <= x; i++)
          if(us[i] == 1 && g[i].size() >= 3) kk++;
        edge.clear();
        kol1 = kol = 0;
        dfs(X);
        if(!us[Y]){
          L = mid;
          continue;
        }
        if(kol - 1 == kol1 && kk == 0){
          L = mid;
          continue;
        }
        R = mid;
        continue;
      }
      if(R == 1e9 + 1) return -1;
      else return R;
  }
  else{
    X++;
    Y++;
    if(x <= 3)
        return -1;
    int mx = 0;
    if(X != 1) mx = mp[{1, X}];
    if(Y != 1) mx = max(mx, mp[{1, Y}]);


    if(X != 1) st.erase({mp[{1, X}], pos[{1, X}]});
    if(Y != 1) st.erase({mp[{1, Y}], pos[{1, Y}]});
    
    pair<int, int> p = *st.begin();
    st.erase(st.begin());
    if(X != 1 && Y != 1){
        st.insert(p);
        if(X != 1) st.insert({mp[{1, X}], pos[{1, X}]});
        if(Y != 1) st.insert({mp[{1, Y}], pos[{1, Y}]});
        return max(mx, p.first);
    }
    else{
        pair<int, int> p1 = *st.begin();
        st.insert(p1);
        st.insert(p);
        if(X != 1) st.insert({mp[{1, X}], pos[{1, X}]});
        if(Y != 1) st.insert({mp[{1, Y}], pos[{1, Y}]});
        return max({mx, p.first, p1.first});
    }
  }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 17 ms 7756 KB Output is correct
5 Correct 30 ms 8024 KB Output is correct
6 Correct 36 ms 8280 KB Output is correct
7 Correct 48 ms 8028 KB Output is correct
8 Correct 50 ms 8028 KB Output is correct
9 Execution timed out 2051 ms 53592 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 1048 ms 41800 KB Output is correct
4 Correct 1201 ms 43536 KB Output is correct
5 Correct 1038 ms 42572 KB Output is correct
6 Correct 1008 ms 43428 KB Output is correct
7 Correct 1076 ms 42988 KB Output is correct
8 Correct 1049 ms 41684 KB Output is correct
9 Correct 1081 ms 42776 KB Output is correct
10 Correct 1034 ms 41436 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 17 ms 7756 KB Output is correct
5 Correct 30 ms 8024 KB Output is correct
6 Correct 36 ms 8280 KB Output is correct
7 Correct 48 ms 8028 KB Output is correct
8 Correct 50 ms 8028 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Incorrect 41 ms 7972 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 17 ms 7756 KB Output is correct
6 Correct 30 ms 8024 KB Output is correct
7 Correct 36 ms 8280 KB Output is correct
8 Correct 48 ms 8028 KB Output is correct
9 Correct 50 ms 8028 KB Output is correct
10 Execution timed out 2051 ms 53592 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 17 ms 7756 KB Output is correct
5 Correct 30 ms 8024 KB Output is correct
6 Correct 36 ms 8280 KB Output is correct
7 Correct 48 ms 8028 KB Output is correct
8 Correct 50 ms 8028 KB Output is correct
9 Execution timed out 2051 ms 53592 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 17 ms 7756 KB Output is correct
6 Correct 30 ms 8024 KB Output is correct
7 Correct 36 ms 8280 KB Output is correct
8 Correct 48 ms 8028 KB Output is correct
9 Correct 50 ms 8028 KB Output is correct
10 Execution timed out 2051 ms 53592 KB Time limit exceeded
11 Halted 0 ms 0 KB -