oj.uz

Submission #342802

# Submission time Handle Problem Language Result Execution time Memory
342802 2021-01-02T20:58:59 Z aryan12 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 19352 KB 
#include <bits/stdc++.h>
using namespace std;
#include "swap.h"

const int MAXN = 1e5 + 10;
int n, m;
vector<pair<int, int> > g[MAXN];
vector<int> from, to, weights;
vector<int> SecondOne[MAXN];
int paths[MAXN];
bool vis[MAXN];

void dfs(int node, int par) {
    vis[node] = true;
    for(int i = 0; i < SecondOne[node].size(); i++) {
        if(SecondOne[node][i] == par)
            continue;
        paths[SecondOne[node][i]]++;
        if(!vis[SecondOne[node][i]])
            dfs(SecondOne[node][i], node);
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for(int i = 0; i < MAXN; i++) {
        g[i].clear();
    }
    n = N;
    m = M;
    for(int i = 0; i < U.size(); i++) {
        from.push_back(U[i]);
        to.push_back(V[i]);
        weights.push_back(W[i]);
        g[U[i]].push_back({W[i], V[i]});
        g[V[i]].push_back({W[i], U[i]});
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    //cout << "Coming here with X = " << X << ", Y = " << Y << endl;
    int l = 1, r = 1e9;
    int mid;
    int ans = -1;
    while(l <= r) {
        for(int i = 0; i < MAXN; i++) {
            vis[i] = false;
            SecondOne[i].clear();
            paths[i] = 0;
        }
        paths[X] = 1;
        mid = (l + r) / 2;
        //cout << "l = " << l << ", mid = " << mid << ", r = " << r << endl;
        for(int i = 0; i < from.size(); i++) {
            if(weights[i] <= mid) {
                SecondOne[from[i]].push_back(to[i]);
                SecondOne[to[i]].push_back(from[i]);
            }
        }
        dfs(X, -1);
        if(paths[X] >= 2 && vis[Y]) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return ans;
}

Compilation message

swap.cpp: In function 'void dfs(int, int)':
swap.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0; i < SecondOne[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0; i < U.size(); i++) {
      |                    ~~^~~~~~~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i = 0; i < from.size(); i++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5484 KB Output is correct
2 Correct 9 ms 5484 KB Output is correct
3 Correct 24 ms 5484 KB Output is correct
4 Correct 31 ms 5612 KB Output is correct
5 Correct 29 ms 5612 KB Output is correct
6 Correct 35 ms 5612 KB Output is correct
7 Correct 37 ms 5612 KB Output is correct
8 Correct 36 ms 5612 KB Output is correct
9 Correct 573 ms 17336 KB Output is correct
10 Correct 1576 ms 19312 KB Output is correct
11 Execution timed out 2068 ms 19352 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5484 KB Output is correct
2 Correct 9 ms 5484 KB Output is correct
3 Execution timed out 2082 ms 17376 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5484 KB Output is correct
2 Correct 9 ms 5484 KB Output is correct
3 Correct 9 ms 5484 KB Output is correct
4 Correct 24 ms 5484 KB Output is correct
5 Correct 31 ms 5612 KB Output is correct
6 Correct 29 ms 5612 KB Output is correct
7 Correct 35 ms 5612 KB Output is correct
8 Correct 37 ms 5612 KB Output is correct
9 Correct 36 ms 5612 KB Output is correct
10 Incorrect 29 ms 5612 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5484 KB Output is correct
2 Correct 9 ms 5484 KB Output is correct
3 Correct 9 ms 5484 KB Output is correct
4 Correct 24 ms 5484 KB Output is correct
5 Correct 31 ms 5612 KB Output is correct
6 Correct 29 ms 5612 KB Output is correct
7 Correct 35 ms 5612 KB Output is correct
8 Correct 37 ms 5612 KB Output is correct
9 Correct 36 ms 5612 KB Output is correct
10 Correct 573 ms 17336 KB Output is correct
11 Correct 1576 ms 19312 KB Output is correct
12 Execution timed out 2068 ms 19352 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5484 KB Output is correct
2 Correct 9 ms 5484 KB Output is correct
3 Correct 24 ms 5484 KB Output is correct
4 Correct 31 ms 5612 KB Output is correct
5 Correct 29 ms 5612 KB Output is correct
6 Correct 35 ms 5612 KB Output is correct
7 Correct 37 ms 5612 KB Output is correct
8 Correct 36 ms 5612 KB Output is correct
9 Correct 573 ms 17336 KB Output is correct
10 Correct 1576 ms 19312 KB Output is correct
11 Execution timed out 2068 ms 19352 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5484 KB Output is correct
2 Correct 9 ms 5484 KB Output is correct
3 Correct 9 ms 5484 KB Output is correct
4 Correct 24 ms 5484 KB Output is correct
5 Correct 31 ms 5612 KB Output is correct
6 Correct 29 ms 5612 KB Output is correct
7 Correct 35 ms 5612 KB Output is correct
8 Correct 37 ms 5612 KB Output is correct
9 Correct 36 ms 5612 KB Output is correct
10 Correct 573 ms 17336 KB Output is correct
11 Correct 1576 ms 19312 KB Output is correct
12 Execution timed out 2068 ms 19352 KB Time limit exceeded
13 Halted 0 ms 0 KB -