oj.uz

답안 #342802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342802 2021-01-02T20:58:59 Z aryan12 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -