Submission #639614

#	Time	Username	Problem	Language	Result	Execution time	Memory
639614		Sofiatpc	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	30 / 100	3090 ms	37364 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define fi first
#define sc second

const int MAXN = 500005;
vector< pair<int,int> > adj[MAXN];
int qtd[MAXN], visQtd;

void dfs(int S, int o)
{
    if(qtd[S]==-1)visQtd++;
    qtd[S]=o;
    for(int i = 0; i < (int)adj[S].size(); i++)
    {
        int viz = adj[S][i].fi, tipo = adj[S][i].sc;
        if(qtd[viz]>=qtd[S])continue;
        if(tipo==1)
        {
            if(o==0)continue;
            dfs(viz,0);
        }
        else dfs(viz,o);
    }
    return;
}

int main()
{
   int N,M; cin>>N>>M;
   for(int i = 1; i <= M; i++)
   {
       char c; int x,y,t=0;
       cin>>x>>y>>c;
       if(c=='A')t=1;
       adj[x].pb({y,t});
       adj[y].pb({x,t});
   }

   int ans = 0;
   for(int s = 1; s <= N; s++)
   {
       for(int i = 1; i <= N; i++)qtd[i]=-1;
       visQtd=0;

       dfs(s,1);

       if(visQtd==N)ans++;
   }

   cout<<ans<<"\n";
}

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