Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 931 Trilant  (Citit de 7354 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
raduzer
Client obisnuit
**

Karma: 62
Deconectat Deconectat

Mesaje: 71



Vezi Profilul
« : Noiembrie 15, 2009, 15:19:16 »

Aici puteti discuta despre problema Trilant.
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #1 : 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.
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #2 : Noiembrie 15, 2009, 22:31:30 »

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.

Tu faci Roy Floyd pe 100 000 de noduri ?
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #3 : 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.
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #4 : 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).
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #5 : 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
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #6 : Noiembrie 16, 2009, 01:07:33 »

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.
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #7 : Noiembrie 16, 2009, 09:45:49 »

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

Nu intra . Very Happy Era ceva gresit la reconstituire.
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #8 : Februarie 02, 2010, 19:21:15 »

A tercut ceva timp, va mai aparea articol cu solutii la .com 2009?
Memorat
mathboy
Moderatori infoarena
Nu mai tace
*****

Karma: 150
Deconectat Deconectat

Mesaje: 259



Vezi Profilul
« Răspunde #9 : Februarie 02, 2010, 19:31:11 »

Uite aici solutiile: http://infoarena.ro/dot-com/2009/solutii/runda-1.
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #10 : Februarie 02, 2010, 19:44:46 »

Multumesc mult Dragos, nu l-am gasit in articole si am crezut ca nu este redactat.
Memorat
Mitza444
Client obisnuit
**

Karma: 6
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #11 : 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;
}
« Ultima modificare: Octombrie 13, 2012, 20:36:53 de către Vidrean Mihai » Memorat
Mitza444
Client obisnuit
**

Karma: 6
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #12 : 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 Brick wall.(desi evaluatoru imi arata ca folosesc mai putina memorie ca la alte teste si nu vad nici o greseala)
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #13 : Octombrie 13, 2012, 23:11:37 »

Testele din arhivă nu se fac publice.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Mitza444
Client obisnuit
**

Karma: 6
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #14 : 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;
}
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #15 : 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! Smile
Memorat
Mitza444
Client obisnuit
**

Karma: 6
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #16 : 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. Winner 1st place
Memorat
lucian666
Client obisnuit
**

Karma: 16
Deconectat Deconectat

Mesaje: 84



Vezi Profilul
« Răspunde #17 : Octombrie 15, 2012, 12:07:07 »

 Smile Salut
Am facut problema cu Dijkstra cu heap si iau doar 70 pct. cu 3 Drum invalid  Cry .Am pus long long unde e nevoie insa nu stiu unde as putea gresi Brick wall.
Vreo sugestie ceva?
Multumesc  Smile
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #18 : 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
Memorat
lucian666
Client obisnuit
**

Karma: 16
Deconectat Deconectat

Mesaje: 84



Vezi Profilul
« Răspunde #19 : Octombrie 15, 2012, 14:45:36 »

 Very Happy Mersi mult Radu.Cu ajutorul observatiilor tale am luat 100 Yahoo!
Memorat
Fayed
Client obisnuit
**

Karma: -24
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #20 : 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.
Memorat
Mihai22e
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #21 : Iulie 18, 2013, 12:34:18 »

Pe testul
Cod:
14 15
1 2 5
1 4 9
2 3 3
2 14 8
3 4 4
4 5 8
5 6 10
5 8 7
6 7 11
8 11 2
8 13 10
8 12 9
11 13 14
11 12 15
11 14 10

imi da (cu sursa de 100p)
Cod:
24
2 4 1
3 4 3 2
2 4 5
Memorat
Zenus
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 10



Vezi Profilul
« Răspunde #22 : 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
Memorat
japjappedulap
Strain
*

Karma: 1
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #23 : 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
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #24 : 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.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines