Submission #1139813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139813		gramathegod	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	3096 ms	28084 KiB

menesinis_bilietas

#include <iostream>
#include <vector>
#include <queue>

#define MAX 500005

using namespace std;

int n, m, ok = 1;

vector<vector<pair<int, int>>> graph(MAX);

void add(vector<vector<pair<int, int>>> &graph, int u, int v, int w) {
    graph[u].emplace_back(v, w);
    graph[v].emplace_back(u, w);
}

bool check[MAX];

void bfs(int init) {
    vector<char> cost(MAX, 0);
    vector<bool> visited(MAX, 0);
    int u, s, v, vw;
    queue<int> q;
    pair<int, int> nou;
    q.push(init);
    cost[init] = 0;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        s = graph[u].size();
        for (int i = 0; i < s; i++) {
            nou = graph[u][i];
            v = nou.first;
            vw = nou.second;
            if (!visited[v] || cost[v] > cost[u] + vw) {
                visited[v] = true;
                cost[v] = cost[u] + vw;
                q.push(v);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (visited[i] == false) {
            check[init] = true;
            ok = 0;
        }
        if (cost[i] > 1) {
            check[init] = true;
            check[i] = true;
        }
    }
}

int main() {
    int result = 0, u, v, w;
    char c;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        cin.get();
        cin.get(c);
        if (c == 'A') {
            w = 1;  // bus
        } else {
            w = 0;  // train
        }
        add(graph, u, v, w);
    }
    for (int i = 1; i <= n; i++) {
        if (!check[i]) {
            bfs(i);
        }
        if (!check[i]) {
            result++;
        }
    }
    if (!ok) {
        result = 0;
    }

    printf("%d", result);
    return 0;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
menesinis_bilietas.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 6
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 19