Submission #1139753

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

menesinis_bilietas

///https://vjudge.net/contest/686817/problemPdf/B?descKey=2714837699882176
/// lithuanian informatics olympiad, national round, 23rd of march 2018, grades X-XII
#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;
            ///printf("lalalala");
        }
        if (cost[i]>1){
            check[init]=true;
            check[i]=true;
            ///printf("lalalala");
        }
    }

}

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:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d", &n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
menesinis_bilietas.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         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