Imprimă pagina - 931 Trilant

Titlul: 931 Trilant
Scris de: Radu Zernoveanu din Noiembrie 15, 2009, 15:19:16

Aici puteti discuta despre problema Trilant (http://infoarena.ro/problema/trilant).

Titlul: Răspuns: 931 Trilant
Scris de: George Popoiu din Noiembrie 15, 2009, 16:02:31

iau 0 si nu stiu de ce... Fac roy floyd, dupa care caut nodul pentru care costul trilantului este minim, dupa care refac drumul recursiv.

Evaluatorul spune ca nu refac drumul complet.. Puteti da un test mai mare? Pe testele care le dau eu merge.

Titlul: Răspuns: 931 Trilant
Scris de: Pripoae Teodor Anton din Noiembrie 15, 2009, 22:31:30

Citat din mesajul lui: Popoiu George din Noiembrie 15, 2009, 16:02:31

Tu faci Roy Floyd pe 100 000 de noduri ?

Titlul: Răspuns: 931 Trilant
Scris de: George Popoiu din Noiembrie 15, 2009, 23:24:38

Citat

u faci Roy Floyd pe 100 000 de noduri ?

Nop, in problema se specifica ca 50% din teste au N<=1000, si intr-adevar, pe 8 teste iau Memory limit exceeded.

Titlul: Răspuns: 931 Trilant
Scris de: Savin Tiberiu din Noiembrie 15, 2009, 23:29:51

Roy floyd nu iti intra nici pentru N < 1000. Ti-ar trebui N < 100. (Roy Floyd e N^3). Vezi poate gresesti la reconstituire (acolo mi se pare ca ai putea gresi).

Titlul: Răspuns: 931 Trilant
Scris de: George Popoiu din Noiembrie 15, 2009, 23:43:41

Citat

Ti-ar trebui N < 100. (Roy Floyd e N^3).

Pe 7 teste imi afiseaza ca nu reconstitui corect, si pe restul Memory exceeded si TLE, sa inteleg ca pe 7 teste N<100 ?

O sa mai verific la reconstituire ... :fool:

Titlul: Răspuns: 931 Trilant
Scris de: Savin Tiberiu din Noiembrie 16, 2009, 01:07:33

Citat din mesajul lui: Popoiu George din Noiembrie 15, 2009, 23:43:41

Citat

Ti-ar trebui N < 100. (Roy Floyd e N^3).

Pe 7 teste imi afiseaza ca nu reconstitui corect, si pe restul Memory exceeded si TLE, sa inteleg ca pe 7 teste N<100 ?

O sa mai verific la reconstituire ... :fool:

In cazul asta verifica implementarea de la Roy Floyd. Ceva nu ai facut bine. Nu ar fi trebuit sa iti intre in timp pe asa multe teste.

Titlul: Răspuns: 931 Trilant
Scris de: George Popoiu din Noiembrie 16, 2009, 09:45:49

Citat

Nu ar fi trebuit sa iti intre in timp pe asa multe teste.

Nu intra . :D Era ceva gresit la reconstituire.

Titlul: Răspuns: 931 Trilant
Scris de: George Popoiu din Februarie 02, 2010, 19:21:15

A tercut ceva timp, va mai aparea articol cu solutii la .com 2009?

Titlul: Răspuns: 931 Trilant
Scris de: Dragos-Alin Rotaru din Februarie 02, 2010, 19:31:11

Uite aici solutiile: http://infoarena.ro/dot-com/2009/solutii/runda-1 (http://infoarena.ro/dot-com/2009/solutii/runda-1).

Titlul: Răspuns: 931 Trilant
Scris de: George Popoiu din Februarie 02, 2010, 19:44:46

Multumesc mult Dragos, nu l-am gasit in articole si am crezut ca nu este redactat.

Titlul: Răspuns: 931 Trilant
Scris de: Vidrean Mihai din Octombrie 13, 2012, 11:08:49

Iau 0p dar nu inteleg ce gresesc.Am facut un Dijkstra din fiecare nod A,B,C si am retinut distantele minime in 3 vector da,db,dc si varful de pe unde s-a trecut pt. a ajunge in varful curent l-am retinut in pa,pb,pc.Am parcurs nodurile si am retinut cea mai mica suma da+db+dc(solutia) si nodul in care este suma minima pt. reconstituire.Pe exemplu merge bine,dar pe testele celelate primesc cost prea mare,drumurile au noduri comune,muchii invalide sau Killed by signal 11.

Multumesc.

Sursa mea:

Cod:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define pp pair<int,int>
#define ff first
#define ss second
#define inf 4000000*10
#define nmax 100005
vector <pp> v[nmax];
int da[nmax],db[nmax],dc[nmax],n;
int pa[nmax],pb[nmax],pc[nmax];
int H[nmax],poz[nmax],sol[nmax];
inline int left_son(int k){
    return 2*k;
}
inline int right_son(int k){
    return 2*k+1;
}
inline int father(int k){
    return k/2;
}
void percolate(int k,int d[]){
    while(k>1 && d[H[k]]<d[H[father(k)]]){
        swap(poz[H[k]],poz[H[father(k)]]);
        swap(H[k],H[father(k)]);
        k=father(k);
    }
}
void sift(int k,int d[],int hp){
    int son;
    do{
        son=0;
        if(left_son(k)<=hp)
            son=left_son(k);
        if(right_son(k)<=hp && d[H[right_son(k)]]<d[H[son]])
            son=right_son(k);
        if(d[H[son]]>d[H[k]])
            son=0;
        if(son){
            swap(poz[H[k]],poz[H[son]]);
            swap(H[k],H[son]);
            k=son;
        }
    }while(son);
}
int minimum(int& hp,int d[] ){
    int key;
    key=H[1];
    swap(poz[H[1]],poz[H[hp]]);
    H[1]=H[hp--];
    sift(1,d,hp);
    return key;
}
void build_heap(int k,int hp){
    int i;
    for(i=1;i<=hp;i++)
        H[i]=poz[i]=i;
    if(poz[k]!=1){
        swap(poz[H[1]],poz[H[k]]);
        swap(H[1],H[k]);
    }
}
void Dijkstra(int nod,int d[],int p[]){
    pp aux;
    int vfmin,dmin,hp,i;
    unsigned j;
    hp=n;
    for(i=1;i<=n;i++)
        d[i]=inf;
    d[nod]=0;
    build_heap(nod,hp);
    p[nod]=-1;
    for(i=1;i<=n;i++){
        vfmin=minimum(hp,d);
        dmin=d[vfmin];
        for(j=0;j<v[vfmin].size();j++){
            aux=v[vfmin][j];
            if(dmin+aux.ss<d[aux.ff]){
                d[aux.ff]=dmin+aux.ss;
                percolate(poz[aux.ff],d);
                p[aux.ff]=vfmin;
            }
        }
    }
}
int main(){
    int m,A,B,C,i,p,q,t,trmin=inf,sum,ind,j;
    freopen("trilant.in","r",stdin);
    scanf("%d%d",&n,&m);
    scanf("%d%d%d",&A,&B,&C);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&p,&q,&t);
        v[p].push_back(make_pair(q,t));
        v[q].push_back(make_pair(p,t));
    }
    fclose(stdin);
    Dijkstra(A,da,pa);
    Dijkstra(B,db,pb);
    Dijkstra(C,dc,pc);
    for(i=1;i<=n;i++){
        sum=da[i]+db[i]+dc[i];
        if(sum<trmin)
            trmin=sum,ind=i;
    }
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pa[j];
	}while(j!=-1);
    freopen("trilant.out","w",stdout);
    printf("%d",trmin);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pb[j];
	}while(j!=-1);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pc[j];
	}while(j!=-1);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
    fclose(stdout);
    return 0;
}

Titlul: Răspuns: 931 Trilant
Scris de: Vidrean Mihai din Octombrie 13, 2012, 20:42:40

Se poate sa-mi trimiteti unul din testele 18,19,20 fisierul in si out ?Orice modificare am facut tot Killed by signal 11(SIGSEGV) iau ](*,).(desi evaluatoru imi arata ca folosesc mai putina memorie ca la alte teste si nu vad nici o greseala)

Titlul: Răspuns: 931 Trilant
Scris de: Andrei Grigorean din Octombrie 13, 2012, 23:11:37

Testele din arhivă nu se fac publice.

Titlul: Răspuns: 931 Trilant
Scris de: Vidrean Mihai din Octombrie 14, 2012, 14:14:42

Ok nu stiam ca testele nu se fac publice. :ok:
Am mai incercat sa gasesc greseala si cred ca este la reconstituirea drumului.Eu am atribuit -1 pozitiei nodul din care pornesc si la restul pozitiilor varful din care s-a ajuns in nodul curent i.Exemplu pentru reconstituirea drumului din A am facut urmatoarea:

Cod:

j=ind;i=0;//ind e varful un suma distantelor e minima
	while(j!=pa[A]){//pa retine varful din care s-a ajuns in nodul i
		sol[++i]=j;
		j=pa[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);

Daca in while in loc de j!=pa[A] care este -1 puneam j>0 nu mai luam Killed by signal 11(SIGSEGV),dar luam ca drum trebuie sa se termine cu A,B sau C.Nu imi dau seama ce operatie face reconstituirea incat sa ia Killed by signal 11(SIGSEGV) pt. ca la memorie e ok.
Aici e sursa completa:

Cod:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define pp pair<int,int>
#define ff first
#define ss second
#define inf 100000000
#define nmax 100005
vector <pp> v[nmax];
int da[nmax],db[nmax],dc[nmax],n;
int pa[nmax],pb[nmax],pc[nmax];
int H[nmax],poz[nmax],sol[nmax];
inline int left_son(int k){
    return 2*k;
}
inline int right_son(int k){
    return 2*k+1;
}
inline int father(int k){
    return k/2;
}
void percolate(int k,int d[]){
    while(k>1 && d[H[k]]<d[H[father(k)]]){
        swap(poz[H[k]],poz[H[father(k)]]);
        swap(H[k],H[father(k)]);
        k=father(k);
    }
}
void sift(int k,int d[],int hp){
    int son;
    do{
        son=0;
        if(left_son(k)<=hp)
            son=left_son(k);
        if(right_son(k)<=hp && d[H[right_son(k)]]<d[H[son]])
            son=right_son(k);
        if(d[H[son]]>d[H[k]])
            son=0;
        if(son){
            swap(poz[H[k]],poz[H[son]]);
            swap(H[k],H[son]);
            k=son;
        }
    }while(son);
}
int minimum(int& hp,int d[] ){
    int key;
    key=H[1];
    swap(poz[H[1]],poz[H[hp]]);
    H[1]=H[hp--];
    sift(1,d,hp);
    return key;
}
void build_heap(int k,int hp){
    int i;
    for(i=1;i<=hp;i++)
        H[i]=poz[i]=i;
    if(poz[k]!=1){
        swap(poz[H[1]],poz[H[k]]);
        swap(H[1],H[k]);
    }
}
void Dijkstra(int nod,int d[],int p[]){
    pp aux;
    int vfmin,dmin,hp,i;
    unsigned j;
    hp=n;
    for(i=1;i<=n;i++)
        d[i]=inf;
    d[nod]=0;
    build_heap(nod,hp);
    p[nod]=-1;
    for(i=1;i<=n;i++){
        vfmin=minimum(hp,d);
        dmin=d[vfmin];
        for(j=0;j<v[vfmin].size();j++){
            aux=v[vfmin][j];
            if(dmin+aux.ss<d[aux.ff]){
                d[aux.ff]=dmin+aux.ss;
				p[aux.ff]=vfmin;
                percolate(poz[aux.ff],d);
            }
        }
    }
}
int main(){
    int m,A,B,C,i,p,q,t,trmin,sum,ind=0,j,k;
    freopen("trilant.in","r",stdin);
    scanf("%d%d",&n,&m);
    scanf("%d%d%d",&A,&B,&C);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&p,&q,&t);
        v[p].push_back(make_pair(q,t));
        v[q].push_back(make_pair(p,t));
    }
    fclose(stdin);
    Dijkstra(A,da,pa);
    Dijkstra(B,db,pb);
    Dijkstra(C,dc,pc);
	trmin=da[1]+db[1]+dc[1];ind=1;
    for(i=2;i<=n;i++){
        sum=da[i]+db[i]+dc[i];
        if(sum<trmin){
            trmin=sum;
			ind=i;
		}
    }
    freopen("trilant.out","w",stdout);
    printf("%d",trmin);
	j=ind;i=0;
	while(j!=pa[A]){
		sol[++i]=j;
		j=pa[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
	j=ind;i=0;
	while(j!=pb[B]){
		sol[++i]=j;
		j=pb[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
	j=ind;i=0;
	while(j!=pc[C]){
		sol[++i]=j;
		j=pc[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
    fclose(stdout);
    return 0;
}

Titlul: Răspuns: 931 Trilant
Scris de: Tudor Tiplea din Octombrie 14, 2012, 18:59:00

Salut!

Costurile din Dijkstra pot ajunge destul de mari, tinand cont de faptul ca muchiile pot fi si 4*10^6, asa ca pune long long unde e nevoie si fa constanta INF mai mare (gen 5*10^11). Bafta! :)

Titlul: Răspuns: 931 Trilant
Scris de: Vidrean Mihai din Octombrie 14, 2012, 21:06:00

Multumesc foarte mult Tiplea Tudor!!!Am facut cum ai spus tu si am pus 5*10^11 la inf si a mers. :yahoo:
Totusi mi se pare ciudat ca merge deoarece mie pe Mingw nu-mi compileaza cu 5*10^11,pentru ca spune ca imi da error: integer constant is too large for "long" type,dar totusi pe site merge.
Multumesc inca o data nu mi-as fi dat seama niciodata. :winner1:

Titlul: Răspuns: 931 Trilant
Scris de: Vasilut Lucian din Octombrie 15, 2012, 12:07:07

:) Salut
Am facut problema cu Dijkstra cu heap si iau doar 70 pct. cu 3 Drum invalid :'( .Am pus long long unde e nevoie insa nu stiu unde as putea gresi ](*,).
Vreo sugestie ceva?
Multumesc :)

Titlul: Răspuns: 931 Trilant
Scris de: Visan Radu din Octombrie 15, 2012, 14:01:39

Pune long long la set (unde ai costul), la iterator si in dijkstra unde faci int val = I->f, trebuie long long val = I->f. De asemenea, mai adauga 2 zero-uri la inf, e prea mica valoarea care ai pus-o. Cu aceste modificari vei lua 100. :ok:

Titlul: Răspuns: 931 Trilant
Scris de: Vasilut Lucian din Octombrie 15, 2012, 14:45:36

:D Mersi mult Radu.Cu ajutorul observatiilor tale am luat 100 :yahoo:

Titlul: Răspuns: 931 Trilant
Scris de: Stratulat Alexandru din Februarie 28, 2013, 16:42:04

Imi poate da cineva si mie un exemplu mai mare sa vad ce nu imi merge ? Mie imi da costul prea mare.

Titlul: Răspuns: 931 Trilant
Scris de: Mihai Ionut Enache din Iulie 18, 2013, 12:34:18

Pe testul

Cod:

imi da (cu sursa de 100p)

Cod:

Titlul: Răspuns: 931 Trilant
Scris de: Tudor Costin Razvan din Septembrie 10, 2014, 21:12:13

Imi poate spune si mie cineva ce gresesc la urmatoarea sursa?? (presupun ca gresesc la reconstituire dar nu stiu ce...) http://www.infoarena.ro/job_detail/1227621?action=view-source

Titlul: Răspuns: 931 Trilant
Scris de: Potra Vlad din Februarie 11, 2015, 21:32:22

Alta problema faina stricata din cauza limitelor. Voi nu vreti sa lasati problema curata, vreti s-o frecati cat mai tare cu tipuri de date care sa primeasca 100 din bulan. Gandesti ca va scarpinati la monitor sa mor io

Titlul: Răspuns: 931 Trilant
Scris de: Mihai Calancea din Februarie 11, 2015, 23:41:04

Nu înțeleg la ce te referi. N-avem nicio intenție să stricăm nimic, nu trebuie să fii agresiv.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Radu Zernoveanu din Noiembrie 15, 2009, 15:19:16