Why is my code not working - Graph Probem


#1

Link to the problem: http://coj.uci.cu/24h/problem.xhtml?pid=2743

Why is my code not working, please help:

#include <bits/stdc++.h>


using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;


bool v[3001];
vi g[3001];

int in_c[3001];
int out_c[3001];

//Should have checked if there is one component that has all the streets
//But didn't changed anything when I removed g so I removed it
set<pi> s;
void dfs(int n){
        v[n] = 1;
        for(auto& i : g[n]){
                s.erase(make_pair(min(i, n), max(i, n)));
                if(!v[i]) dfs(i);
        }
}

int main() {
        	ios_base::sync_with_stdio(false); 
        	cin.tie(nullptr); 
        	cout.tie(nullptr); 
        	cerr.tie(nullptr);	

        int t; cin >> t;
        for(;t;--t){
                int n, m;
                cin >> n >> m;

                //CLEAN ALL THE THINGS
                s = set<pi>();
                for(auto i = 0; i < n; ++i) in_c[i] = out_c[i] = v[i] = 0;
                for(auto i = 0; i < m; ++i){
                        int u, v;
                        cin >> u >> v;
                        --u; --v;

                        //didn't change anuthing but still is here
                        g[u].push_back(v);
                        g[v].push_back(u);
                        s.insert(make_pair(min(u, v), max(u, v)));

                        //Ulazi u u
                        //Enters in u
                       //Gets out of v
                        ++out_c[u];
                        ++in_c[v];
                }

                int odd = 0;
                int pos = 0;
                int neg = 0;
                for(auto i = 0; i < n; ++i){
                        //Score for every
                        int tmp = out_c[i] - in_c[i];
                        //Degree for every
                        int deg = out_c[i] + in_c[i];

                        //Pos is the number of positive (starts)
                        //Neg is the number of negative (ends)
                        (tmp > 0 ? pos : neg) += abs(tmp);

                        //Counts odd degree
                        if(deg%2) ++odd;
                }

                //If the number of ends is 1 and starts 1 (directed path) or 0 (cycle) then its ok
                if((pos == 0 && neg == 0) || (pos == 1 && neg == 1)) cout << "YES\n";
                //If not, is there undirected path (2 odd) or cycle (0) simple math
                else if((odd == 0 || odd == 2)) cout << "TRAFFIC STOPPING NEEDED\n";
                //If none of above then its the third one
                else cout << "WAKE UP EARLIER\n";
        }
}

#2

Hello @sprdalo, should be nice if you gave us info related to the current error messages you are facing since it helps us to check what it can be.

Also some english explanation on the code because it is in Polish I think?

Thanks


#3

I get many WA (Wrong Answer). It is not Polish lol, it is Serbian, I will translate it in a minute, sorry about that!


#4

I am a bit confused on how the problem is supposed to work, but so far, given the ammount of cases (T) and using the example code plus more cases (T=5), I got something like this:

I am not a expert on C++ but did some little fixes to the code to improve readibility.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

bool v[3001];
vi g[3001];

int in_c[3001];
int out_c[3001];

//Trebalo je da proveri da li postoji jedna povezana komponenta koja ima sve ulice
//Ali nista nije menjalo kad sam g sklonio pa sam ga sklonio
set<pi> s;
void dfs(int n)
{
  v[n] = 1;
  for(auto& i : g[n])
  {
    s.erase(make_pair(min(i, n), max(i, n)));
    if(!v[i]) {
      dfs(i);
    }
  }
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	cerr.tie(nullptr);	

  int t; cin >> t;
  for(;t;--t)
  {
    int n, m;
    cin >> n >> m;

    //CLEAN ALL THE TINGS
    s = set<pi>();
    for(auto i = 0; i < n; ++i) {
      in_c[i] = out_c[i] = v[i] = 0;
    }
    for(auto i = 0; i < m; ++i)
    {
      int u, v;
      cin >> u >> v;
      --u; --v;

      //bilo pa video da ne menja broj primera pa sad nicemu ne sluzi
      g[u].push_back(v);
      g[v].push_back(u);
      s.insert(make_pair(min(u, v), max(u, v)));

      //Ulazi u u
      //Izlazi iz v
      ++out_c[u];
      ++in_c[v];
    }

    int odd = 0;
    int pos = 0;
    int neg = 0;
    for(auto i = 0; i < n; ++i)
    {
      //Skor za svaki
      int tmp = out_c[i] - in_c[i];
      //Degree za svaki
      int deg = out_c[i] + in_c[i];

      //Pos je broj pozitivnih (pocetaka)
      //Neg je btoj negativnih (krajeva)
      (tmp > 0 ? pos : neg) += abs(tmp);

      //Broji neparne degree
      if(deg%2) ++odd;
    }

    //Ako je broj krajeva 1 i pocetaka 1 (usmerena staza) ili 0 (ciklus) onda je kul
    if((pos == 0 && neg == 0) || (pos == 1 && neg == 1)) {
      cout << "YES\n";
      //Ako nije kul da li postoji neusmerena staza (2 neparna) ili ciklus (0) znas to
    } else if((odd == 0 || odd == 2)) {
      cout << "TRAFFIC STOPPING NEEDED\n";
      //Ako nije ni jedno ni drugo onda je trece
    } else {
      cout << "WAKE UP EARLIER\n";
    }
  }
}

#5

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.