Submission #342802

#	Time	Username	Problem	Language	Result	Execution time	Memory
342802		aryan12	Swapping Cities (APIO20_swap)	C++17	0 / 100	2082 ms	19352 KiB

swap

#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 (stderr)

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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27