Β Φάση 2013

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
hgaoer
Δημοσιεύσεις: 3
Εγγραφή: Παρ Φεβ 08, 2013 12:41 am

Β Φάση 2013

Δημοσίευση από hgaoer »

Αφού λοιπόν τελείωση η Β φάση του διαγωνισμού θα θελα να σας ζητήσω να ποστάρετε μια ενδεικτική "efficient" λύση του προβλήματος σε C++ μιας και δεν μπόρεσα ν βρω λύση που για n=1000000 και m=999999 να υπολογίζει το αποτέλεσμα σε <1sec. Ευχαριστώ εκ των προτέρων.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Β Φάση 2013

Δημοσίευση από pman »

hgaoer έγραψε:Αφού λοιπόν τελείωση η Β φάση του διαγωνισμού θα θελα να σας ζητήσω να ποστάρετε μια ενδεικτική "efficient" λύση του προβλήματος σε C++ μιας και δεν μπόρεσα ν βρω λύση που για n=1000000 και m=999999 να υπολογίζει το αποτέλεσμα σε <1sec. Ευχαριστώ εκ των προτέρων.

Κώδικας: Επιλογή όλων

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>

using namespace std;

#define MAXN 1000001

vector < list < int > > adj(MAXN);

int n , k , from , to , maxu;

int D[MAXN];
bool visited[MAXN];

void dfs ( int u ) {

     stack<int> s;
     
     s.push ( u );
     
     while ( s.empty() == false ) {
     
             int top = s.top();
             s.pop();
             
             if ( visited[top] )
                continue;
             
             visited[top] = true;
             
             for ( list<int>::iterator pos = adj[top].begin(); pos != adj[top].end(); ++pos ) {
                 if ( !visited[*pos] ) {
                    D[*pos] = D[top] + 1;
                    s.push ( *pos );     
                 }    
             }
           
     }
     
}

int main( ) {

    freopen("scidinner.in","r",stdin);
    freopen("scidinner.out","w",stdout);
    
    scanf ( "%d %d" , &n , &k );
    
    while ( k-- ) {
          scanf ( "%d %d" , &from , &to );
          adj[from].push_back ( to );   
    }
    
    for ( int i = 1; i <= n; ++i ) {
        visited[i] = false;
        D[i] = 0;    
    }
    
    for ( int i = 1; i <= n; ++i )
        if ( !visited[i] ) {
           dfs ( i );
        }
    
    maxu = D[1];
    
    for ( int i = 2; i <= n; ++i )
        maxu = max ( maxu , D[i] );

    printf ( "%d\n" , maxu+1 );
    
    return 0;
   
}
Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

Re: Β Φάση 2013

Δημοσίευση από mariosal »

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <vector>
#include <stack>
#include <list>
#include <algorithm>

using namespace std;

struct Edge {
  int trg, depth;
};

int dfs(list<int> *E, int src) {
  int max_depth;
  Edge e;
  stack<Edge> s;
  list<int>::iterator i;

  max_depth = 0;
  s.push((Edge) {src, 1});
  while (!s.empty()) {
    e = s.top();
    s.pop();

    max_depth = max(max_depth, e.depth);
    for (i = E[e.trg].begin(); i != E[e.trg].end(); ++i) {
      s.push((Edge) {*i, e.depth + 1});
    }
  }
  return max_depth;
}

int main() {
  int i, m, max_depth, n, u, v;
  vector<bool> in;
  list<int> *E; // Contains the edges of the graph

#ifdef CONTEST
  freopen("scidinner.in", "r", stdin);
  freopen("scidinner.out", "w", stdout);
#endif

  scanf("%d %d", &n, &m);
  E = new list<int>[n];
  in.reserve(n);

  while (m--) {
    scanf("%d %d", &u, &v);
    if (u != v) { // No edges from a vertex to itself save comparisons in dfs
      E[u - 1].push_back(v - 1);
      in[v - 1] = true; // If there is an edge (u, v), then v is not a root
    }
  }

  max_depth = 0;
  for (i = 0; i < n; ++i) {
    if (!in[i]) { // Starting from roots guarantees visiting all the vertices
      max_depth = max(max_depth, dfs(E, i));
    }
  }
  printf("%d\n", max_depth);

  return 0;
}
hgaoer
Δημοσιεύσεις: 3
Εγγραφή: Παρ Φεβ 08, 2013 12:41 am

Re: Β Φάση 2013

Δημοσίευση από hgaoer »

Thanx
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Β Φάση 2013

Δημοσίευση από infinity »

Κώδικας: Επιλογή όλων

#include <cstdio>      
#include <list>    
#include <set>    
#include <algorithm>      
    
using namespace std;    
    
void bfs(list<int> graph[],int s,int dist[])      
{      
    set<int> st;    
    list<int>::iterator it;    
    st.insert( s );    
    dist[s] = 1;    
    while( !st.empty() ) {    
        int u = *st.begin();    
        st.erase( st.begin() );    
        for( it = graph[u].begin(); it != graph[u].end() ; ++it ) {    
            st.insert( *it );    
            dist[ *it ] = dist[u] + 1;    
        }    
    }    
}    
      
int main(void)      
{      
    freopen("scidinner.in","rt",stdin);      
    freopen("scidinner.out","wt",stdout);       
    int V,E,u,v,ans = 0;      
    scanf("%d%d",&V,&E);     
    int dist[V + 1],indeg[V + 1];     
    for(int i=0; i<=V; i++) {    
        indeg[ i] = dist[ i ] = 0;    
    }    
    list<int> *graph;      
    graph=new list<int>[V+1];    
    for(int i=0; i<E; i++) {      
        scanf("%d%d",&u,&v);    
        if( u != v ) {    
            graph[u].push_back(v);      
            indeg[v] = 1;    
        }
    }      
    for(int i=1; i<=V; i++) {    
        if( indeg[ i ] == 0) {    
            bfs(graph,i,dist);    
        }    
    }    
    for(int i=1; i<=V; i++) {    
        if( dist[i] > ans ) {    
            ans = dist[i];    
        }    
    }    
    printf("%d\n",ans);      
    return 0;      
}
Markos
Δημοσιεύσεις: 2
Εγγραφή: Σάβ Φεβ 09, 2013 3:06 pm

Re: Β Φάση 2013

Δημοσίευση από Markos »

Γεια σας.
Είμαι καινούριος στο Forum, αλλά βλέποντας τη συζήτηση σκέφτηκα να ανεβάσω 2 testcase.
Τι αποτέλεσμα βγάζετε και σε πόσο χρόνο για το καθένα;

1)
100 10
1 2
1 3
3 4
4 5
2 6
5 7
100 1
8 99
6 8
99 10

2)
1000000 5
1 2
3 4
5 6
7 8
9 10

Εγώ βγάζω: 1) 7 ( 0,001s ).
2) 2 ( 0,006s ).
evry
Δημοσιεύσεις: 1
Εγγραφή: Σάβ Φεβ 09, 2013 5:43 pm

Re: Β Φάση 2013

Δημοσίευση από evry »

Οι απαντήσεις σου είναι σωστές. Και εγώ αυτά βγάζω.
Δίνω και εγώ μια λύση η οποία νομίζω ότι εκτός του ότι είναι αρκετά γρήγορη είναι και εξαιρετικά απλή , αφού δεν χρειάζεται ούτε γνώσεις θεωρίας γράφων, ούτε άλλες δομές δεδομένων παρά μόνο έναν πίνακα. Η λύση ουσιαστικά είναι 7-8 γραμμές.
Εκμεταλλεύεται τα ιδιαίτερα χαρακτηριστικά του προβλήματος.
Το αρνητικό είναι ότι ξαναυπολογίζει κάποια μονοπάτια σε αντίθεση με τους γνωστούς αλγορίθμους.Νομίζω όμως ότι αυτό δεν είναι πρόβλημα λόγω του πολύ αραιού γράφου.

Κώδικας: Επιλογή όλων

#include <fstream>
using namespace std;

int dist[1000001], N, M, x, y, longestPath, count;
int main()
{
    ifstream fin("scidinner.in");    ofstream fout("scidinner.out");
    fin >> N >> M;
    for (int i=1; i<=N; i++) 
             dist[i] = 0;
    for (int i=1; i<=M; i++) {
        fin >> x >> y;
        dist[y] = x;
    }
    longestPath=0;
    for (int i=1; i<=N; i++) {
        count = 1;  int j = i;
        while (dist[j]>0) {
            j = dist[j];
            count++;
        }
        if (count>longestPath)
            longestPath = count;
    }
    fout << longestPath << endl;
    return 0;
}
Markos
Δημοσιεύσεις: 2
Εγγραφή: Σάβ Φεβ 09, 2013 3:06 pm

Re: Β Φάση 2013

Δημοσίευση από Markos »

Ευχαριστώ. :D
hgaoer
Δημοσιεύσεις: 3
Εγγραφή: Παρ Φεβ 08, 2013 12:41 am

Re: Β Φάση 2013

Δημοσίευση από hgaoer »

evry έγραψε:Οι απαντήσεις σου είναι σωστές. Και εγώ αυτά βγάζω.
Δίνω και εγώ μια λύση η οποία νομίζω ότι εκτός του ότι είναι αρκετά γρήγορη είναι και εξαιρετικά απλή , αφού δεν χρειάζεται ούτε γνώσεις θεωρίας γράφων, ούτε άλλες δομές δεδομένων παρά μόνο έναν πίνακα. Η λύση ουσιαστικά είναι 7-8 γραμμές.
Εκμεταλλεύεται τα ιδιαίτερα χαρακτηριστικά του προβλήματος.
Το αρνητικό είναι ότι ξαναυπολογίζει κάποια μονοπάτια σε αντίθεση με τους γνωστούς αλγορίθμους.Νομίζω όμως ότι αυτό δεν είναι πρόβλημα λόγω του πολύ αραιού γράφου.

Κώδικας: Επιλογή όλων

#include <fstream>
using namespace std;

int dist[1000001], N, M, x, y, longestPath, count;
int main()
{
    ifstream fin("scidinner.in");    ofstream fout("scidinner.out");
    fin >> N >> M;
    for (int i=1; i<=N; i++) 
             dist[i] = 0;
    for (int i=1; i<=M; i++) {
        fin >> x >> y;
        dist[y] = x;
    }
    longestPath=0;
    for (int i=1; i<=N; i++) {
        count = 1;  int j = i;
        while (dist[j]>0) {
            j = dist[j];
            count++;
        }
        if (count>longestPath)
            longestPath = count;
    }
    fout << longestPath << endl;
    return 0;
}
Evry kai gw kapws etc tolisa alla t problima ein oti se megalo testcase mas koboun logo xronou...Ya N=100000 kai M=99999 bgazei apotelesma gyro st 10 sec kai trexw me i7.
Απάντηση