oj.uz

Submission #532843

# Submission time Handle Problem Language Result Execution time Memory
532843 2022-03-04T05:18:52 Z ohohorz Swapping Cities (APIO20_swap) C++14
37 / 100
 2000 ms 25964 KB 
#include "swap.h"

#include <vector>
#include<set>
#include<algorithm>
#include<climits>
using namespace std;

// #define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define sz(x) (int)x.size()

const int MAXN = 1e5 + 5;
const int INF = INT_MAX;

int n, m;
// vector< pair <int,int> > g[MAXN];
vector< pair<pii,int> > ed;
vector<int> wts;
int deg[MAXN];
int tot, onedeg, twodeg;
bool vis[MAXN];
vector<pii> g[MAXN];
void dfs(int u){
  vis[u] = 1;
  tot ++;
  onedeg += (deg[u] == 1);
  twodeg += (deg[u] == 2);
  for(auto p:g[u]){
    if(!vis[p.first]) 
      dfs(p.first);
  }
} 

bool cmp(pair<pii,int> a, pair<pii,int> b){
  if(a.second < b.second) return 1;
  if(a.second > b.second) return 0;
  return 1;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N,m = M;
  set<int> wt;
  for(int i = 0;i < m;i++){
    int u = U[i] + 1;
    int v = V[i] + 1;
    ed.pb(mp(mp(u, v), W[i]));
    wt.insert(W[i]);
  }
  sort(ed.begin(), ed.end(), cmp);
  for(int gg:wt) wts.pb(gg);
}

int getMinimumFuelCapacity(int X, int Y) {
  X++, Y++;
  int l = 0, r = sz(wts) - 1;
  int ans = INF;

  while(l <= r){
    int md = (l + r) >> 1LL;
    int W = wts[md];
    
    
    for(int i =1;i<=n;i++) g[i].clear(), vis[i] = 0;
    for(int i =1;i<=n;i++) deg[i] = 0;
    for(int i = 0;i<m;i++){
      if(ed[i].second > W) break;
      int u = ed[i].first.first;
      int v = ed[i].first.second;
      int w = ed[i].second;  
      g[u].pb(mp(v, w));
      g[v].pb(mp(u, w));
      deg[u] ++;
      deg[v] ++;
    }
    tot = 0, onedeg = 0, twodeg=0;
    bool ok = 1;
    dfs(X);
    ok &= vis[Y];

    if(!ok){
      l = md + 1;
      continue;
    }
    // connected hai x and y
    if(tot == (onedeg + twodeg) and onedeg == 2 and twodeg == (tot - 2)) ok = 0;
    if(ok==1){
      ans = min(ans, W);
      r = md - 1;
    }else l = md + 1;
  }
  if(ans == INF) return -1;
  return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2508 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 3 ms 2768 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 159 ms 13536 KB Output is correct
10 Correct 385 ms 15508 KB Output is correct
11 Correct 410 ms 15560 KB Output is correct
12 Correct 518 ms 15944 KB Output is correct
13 Correct 410 ms 16352 KB Output is correct
14 Execution timed out 2050 ms 13800 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2508 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Execution timed out 2025 ms 16544 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2508 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 3 ms 2768 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 2 ms 2628 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2768 KB Output is correct
12 Correct 3 ms 2764 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 4 ms 2640 KB Output is correct
16 Correct 4 ms 2764 KB Output is correct
17 Correct 4 ms 2764 KB Output is correct
18 Correct 3 ms 2764 KB Output is correct
19 Correct 3 ms 2644 KB Output is correct
20 Correct 4 ms 2776 KB Output is correct
21 Correct 4 ms 2764 KB Output is correct
22 Correct 3 ms 2776 KB Output is correct
23 Correct 3 ms 2636 KB Output is correct
24 Correct 5 ms 2764 KB Output is correct
25 Correct 4 ms 2764 KB Output is correct
26 Correct 4 ms 2776 KB Output is correct
27 Correct 3 ms 2764 KB Output is correct
28 Correct 4 ms 2764 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2628 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 3 ms 2768 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 159 ms 13536 KB Output is correct
11 Correct 385 ms 15508 KB Output is correct
12 Correct 410 ms 15560 KB Output is correct
13 Correct 518 ms 15944 KB Output is correct
14 Correct 410 ms 16352 KB Output is correct
15 Correct 3 ms 2636 KB Output is correct
16 Correct 3 ms 2768 KB Output is correct
17 Correct 3 ms 2764 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 4 ms 2640 KB Output is correct
21 Correct 4 ms 2764 KB Output is correct
22 Correct 4 ms 2764 KB Output is correct
23 Correct 3 ms 2764 KB Output is correct
24 Correct 3 ms 2644 KB Output is correct
25 Correct 4 ms 2776 KB Output is correct
26 Correct 4 ms 2764 KB Output is correct
27 Correct 3 ms 2776 KB Output is correct
28 Correct 3 ms 2636 KB Output is correct
29 Correct 5 ms 2764 KB Output is correct
30 Correct 4 ms 2764 KB Output is correct
31 Correct 4 ms 2776 KB Output is correct
32 Correct 3 ms 2764 KB Output is correct
33 Correct 4 ms 2764 KB Output is correct
34 Correct 17 ms 4172 KB Output is correct
35 Correct 434 ms 15124 KB Output is correct
36 Correct 408 ms 14052 KB Output is correct
37 Correct 435 ms 13420 KB Output is correct
38 Correct 461 ms 13172 KB Output is correct
39 Correct 467 ms 13160 KB Output is correct
40 Correct 379 ms 12292 KB Output is correct
41 Correct 425 ms 14920 KB Output is correct
42 Correct 436 ms 14796 KB Output is correct
43 Correct 307 ms 14684 KB Output is correct
44 Correct 495 ms 13836 KB Output is correct
45 Correct 532 ms 19360 KB Output is correct
46 Correct 455 ms 14708 KB Output is correct
47 Correct 542 ms 13308 KB Output is correct
48 Correct 587 ms 14340 KB Output is correct
49 Correct 153 ms 19952 KB Output is correct
50 Correct 130 ms 15732 KB Output is correct
51 Correct 347 ms 16928 KB Output is correct
52 Correct 716 ms 22760 KB Output is correct
53 Correct 575 ms 22772 KB Output is correct
54 Correct 697 ms 25964 KB Output is correct
55 Correct 347 ms 15712 KB Output is correct
56 Correct 853 ms 22064 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2508 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 3 ms 2768 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 159 ms 13536 KB Output is correct
10 Correct 385 ms 15508 KB Output is correct
11 Correct 410 ms 15560 KB Output is correct
12 Correct 518 ms 15944 KB Output is correct
13 Correct 410 ms 16352 KB Output is correct
14 Execution timed out 2050 ms 13800 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2628 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 3 ms 2768 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 159 ms 13536 KB Output is correct
11 Correct 385 ms 15508 KB Output is correct
12 Correct 410 ms 15560 KB Output is correct
13 Correct 518 ms 15944 KB Output is correct
14 Correct 410 ms 16352 KB Output is correct
15 Execution timed out 2050 ms 13800 KB Time limit exceeded
16 Halted 0 ms 0 KB -