Β Φάση 2013
Β Φάση 2013
Αφού λοιπόν τελείωση η Β φάση του διαγωνισμού θα θελα να σας ζητήσω να ποστάρετε μια ενδεικτική "efficient" λύση του προβλήματος σε C++ μιας και δεν μπόρεσα ν βρω λύση που για n=1000000 και m=999999 να υπολογίζει το αποτέλεσμα σε <1sec. Ευχαριστώ εκ των προτέρων.
Re: Β Φάση 2013
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
Κώδικας: Επιλογή όλων
#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;
}
Re: Β Φάση 2013
Κώδικας: Επιλογή όλων
#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;
}
Re: Β Φάση 2013
Γεια σας.
Είμαι καινούριος στο 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 ).
Είμαι καινούριος στο 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 ).
Re: Β Φάση 2013
Οι απαντήσεις σου είναι σωστές. Και εγώ αυτά βγάζω.
Δίνω και εγώ μια λύση η οποία νομίζω ότι εκτός του ότι είναι αρκετά γρήγορη είναι και εξαιρετικά απλή , αφού δεν χρειάζεται ούτε γνώσεις θεωρίας γράφων, ούτε άλλες δομές δεδομένων παρά μόνο έναν πίνακα. Η λύση ουσιαστικά είναι 7-8 γραμμές.
Εκμεταλλεύεται τα ιδιαίτερα χαρακτηριστικά του προβλήματος.
Το αρνητικό είναι ότι ξαναυπολογίζει κάποια μονοπάτια σε αντίθεση με τους γνωστούς αλγορίθμους.Νομίζω όμως ότι αυτό δεν είναι πρόβλημα λόγω του πολύ αραιού γράφου.
Δίνω και εγώ μια λύση η οποία νομίζω ότι εκτός του ότι είναι αρκετά γρήγορη είναι και εξαιρετικά απλή , αφού δεν χρειάζεται ούτε γνώσεις θεωρίας γράφων, ούτε άλλες δομές δεδομένων παρά μόνο έναν πίνακα. Η λύση ουσιαστικά είναι 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;
}
Re: Β Φάση 2013
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.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; }