318 - Domino Effect

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

318 - The judge is wrong

Post by little joey » Mon Jan 20, 2003 1:59 pm

The description says:
If you find several solutions, output only one of them.
Well,

Code: Select all

The last domino falls after 7.5 seconds, between key dominoes 2 and 3.
and

Code: Select all

The last domino falls after 7.5 seconds, between key dominoes 3 and 2.

are both valid solutions to the second example in the problem statement, and nothing is said about the order in which the dominoes should be presented.
The judge only accepts the first :evil:.

There goes another hour of debugging...

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sun May 30, 2004 1:22 am

Also if there's a choice outputting "between X and Y." or "at key domino Z", Then output "at key domino Z."
I'm always willing to help, if you do the same.

orca
New poster
Posts: 4
Joined: Mon Dec 15, 2003 6:48 am

318 - Domino Effect

Post by orca » Sat Nov 12, 2005 3:52 pm

hi
I can't get AC and I don't know why
(I try to solve #318 using "single source shortest path")
Is there any tips? :cry:

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Wed Mar 08, 2006 2:51 am

What if there's a choice between (X and Y) and (A and B), which one do we output?

m7md_3cs_fci
New poster
Posts: 1
Joined: Fri Jul 04, 2008 11:59 am

318 Domino Effect

Post by m7md_3cs_fci » Fri Jul 04, 2008 12:04 pm

Hi everybody,
can anyone send some test cases to test my code, i get 6 WAs in my code and i don't know why
thanks in advance,

Code: Select all

//My code
#include<iostream>
#include<vector>
#include<set>
using namespace std;

long mat[500][500];
vector<int> v[500];
int n,m;
long dist[500];
//int parent[500];
void get(){
	memset(dist , -1 , sizeof dist);
	//memset(parent , -1 , sizeof parent);
	set<pair<long , int> > q;
	q.insert(make_pair(0 ,0 ));
	dist[0] = 0;
	while(!q.empty()){
		pair<long , int> p = *q.begin(); q.erase(q.begin());
		int i = p.second;
		for(int k = 0 ; k<(signed int)v[p.second].size() ; k++){
			int j = v[p.second][k];
			long c = p.first + mat[i][j];
			if(dist[j]==-1 || c<dist[j]){
				dist[j] = c;
				//parent[j] = i;
				q.insert(make_pair(c , j));
			}
		}
	}
}

int main(){
	freopen("1.in" , "rt" , stdin);
	int t = 0;
	while(true){
		cin>>n>>m;
		if(!n&&!m) break;
		t++;
		printf("System #%d\n",t);
		memset(mat , -1 , sizeof mat);
		for(int i = 0 ; i<500 ; i++)
			v[i].clear();
		for(int i = 0 ; i<m ; i++){
			int x , y ;
			long l;
			cin>>x>>y>>l;
			x--;
			y--;
			mat[x][y] = mat[y][x] = l;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		get();
		printf("The last domino falls after ");
		vector<pair<double , pair<int , int> > > vv;
		for(int i = 0 ; i<n ; i++){
			if(dist[i]==-1) continue;
			vv.push_back(make_pair(-dist[i] , make_pair(-1 , i)));
		}
		for(int i = 0 ; i<n ; i++){
			for(int j = i+1 ; j<n;j++){
				if(mat[i][j]==-1) continue;
				if((dist[i]<=dist[j] && dist[i]+mat[i][j]<= dist[j]) || (dist[j]<dist[i] && dist[j]+mat[j][i]<=dist[i])) continue;
				double d = (dist[i]+dist[j]+mat[i][j])/2.0;
				vv.push_back(make_pair(-d , make_pair(i , j)));
			}
		}
		sort(vv.begin() , vv.end());
		pair<double , pair<int , int> > pp = vv[0];
		if(pp.second.first==-1){
			printf("%.1lf seconds, at key domino %d.\n\n" ,(double)-pp.first , pp.second.second+1 );
		}else{
			printf("%.1lf seconds, between key dominoes %d and %d.\n\n" ,(double)-pp.first , pp.second.first+1 , pp.second.second+1 );
		}
	}
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 318 Domino Effect

Post by Jan » Sun Jul 06, 2008 9:36 pm

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

Antono
New poster
Posts: 1
Joined: Tue Apr 21, 2009 9:02 am

318 Domino Effect

Post by Antono » Tue Apr 21, 2009 10:52 pm

I tried to solve this problem. I got WA. Can anybody help me? Thanks. My code is here

Code: Select all

#include <cstdio>
#include <queue>

using namespace std;


struct Domino
{
	int id;
	int time;
	bool in_Queue;
    bool fresh;
};

struct Row
{
	int length;
	bool exists;
};


int main() 
{
	queue<struct Domino *> Q;
	struct Domino dominoes[502];
	Row matrix[502][502];
	
	int n, m;
	int a, b, l;
	bool case_A=false, case_B=false;
	double last=0.0;
	int d1, d2;
	int counter=0;


	for(int i=0;i<502;i++)
	{
		dominoes[i].id=i;
	}

	while(1)
	{
		scanf("%d %d",&n,&m);

		if(n==0 && m==0)
			break;

		for(int i=0;i<=n;i++)
		{
			dominoes[i].fresh=true;
			dominoes[i].in_Queue=false;
			dominoes[i].time=0;
		}

		for(int i=0;i<502;i++)
		{
			for(int j=0;j<502;j++)
			{
				matrix[i][j].exists=false;
			}
		}

		for(int i=0;i<m;i++)
		{
			scanf("%d %d %d",&a, &b, &l);
			a--; b--;
			matrix[a][b].exists=true;
			matrix[a][b].length=l;
			matrix[b][a].exists=true;
			matrix[b][a].length=l;
		}

		dominoes[0].fresh=false;
		dominoes[0].in_Queue=true;
		dominoes[0].time=0;

		Q.push(&dominoes[0]);


		last=0.0;

		while(!Q.empty())
		{
			struct Domino *D_ptr;
			D_ptr=Q.front(); Q.pop();
			

			for(int i=0;i<n;i++)
			{
				if(matrix[D_ptr->id][i].exists)
				{
					if(dominoes[i].fresh)
					{
						dominoes[i].fresh=false; dominoes[i].in_Queue=true; 
						dominoes[i].time=D_ptr->time+matrix[D_ptr->id][i].length;

						if((double)(dominoes[i].time) > last)
						{
							last=(double)(dominoes[i].time); d1=i; case_A=true; case_B=false;
						}

						Q.push(&dominoes[i]);
						continue;
					}

					
					if(D_ptr->time==dominoes[i].time)
					{
						if(((double)matrix[D_ptr->id][i].length/2.0+(double)(D_ptr->time)) > last )
						{
							case_A=false; case_B=true; last=(double)matrix[D_ptr->id][i].length/2.0+(double)D_ptr->time;
							if(i< (D_ptr->id ))
							{
								d1=i; d2=D_ptr->id;
							}
							else
							{
								d1=D_ptr->id; d2=i;
							}
						}
					}


					if((dominoes[i].time) > (D_ptr->time))
					{
						if((dominoes[i].time)> (matrix[D_ptr->id][i].length +D_ptr->time ) )
						{
							dominoes[i].time=matrix[D_ptr->id][i].length +D_ptr->time;
							
							if(dominoes[i].in_Queue==false)
							{
							Q.push(&dominoes[i]);
							dominoes[i].in_Queue=true;
							}
							
							continue;
						}
						
						if((dominoes[i].time) == (matrix[D_ptr->id][i].length +D_ptr->time ) )
						{
							continue;
						}


						if((double(dominoes[i].time)+double(matrix[D_ptr->id][i].length-(dominoes[i].time-D_ptr->time))/2.0)>last)
						{
							last=(double(dominoes[i].time)+double( matrix[D_ptr->id][i].length-(dominoes[i].time-D_ptr->time))/2.0);
							case_B=true;  case_A=false;
							if(i< (D_ptr->id ))
							{
								d1=i; d2=D_ptr->id;
							}
							else
							{
								d1=D_ptr->id; d2=i;
							}

						}

					}


					if((D_ptr->time) > dominoes[i].time)
					{
					
						if((dominoes[i].time+matrix[D_ptr->id][i].length) < D_ptr->time)
						{

							D_ptr->time=dominoes[i].time+matrix[D_ptr->id][i].length;
							i=-1;
							continue;
						}

						if((dominoes[i].time+matrix[D_ptr->id][i].length) == D_ptr->time)
						{
							continue;
						}


						if( ( double(matrix[D_ptr->id][i].length-(D_ptr->time-dominoes[i].time))/2.0 + double(D_ptr->time)  )  >last )
						{
							last= double(matrix[D_ptr->id][i].length-(D_ptr->time-dominoes[i].time))/2.0 + double(D_ptr->time); 
							case_B=true; case_A=false;
							if(i< (D_ptr->id ))
							{
								d1=i; d2=D_ptr->id;
							}
							else
							{
								d1=D_ptr->id; d2=i;
							}

						}

					}


				}
			}
			
			D_ptr->in_Queue=false;

		}

	counter++;
	
	if(counter>=2)
	{
		printf("\n");
	}

	if(case_A)
	{
		printf("System #%d\n",counter);
		printf("The last domino falls after %.1lf seconds, at key domino %d.\n",last,d1 + 1);
	}
	else if(case_B)
	{ 
		printf("System #%d\n",counter);
		printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n",last,d1+1,d2+1);

	}


	}

	return 0;
}


slovenec
New poster
Posts: 1
Joined: Fri May 01, 2009 11:32 am

Re: 318 Domino Effect

Post by slovenec » Fri May 01, 2009 3:58 pm

Hi!

Does anyone have some important/tricky samples for this problem?
I don't expect anyone to read my code, but if someone finds a sample where my algorithm gives wrong answer, I would be very gratefull.

David

Code: Select all


import java.io.*;

public class Main {


	public static void main(String[] args) throws IOException{
		BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));
		int n;
		int m;
		Graf g;
		int[] vr;
		int[] cas;
		String[] s;
		int[] resitev;

		int t;
		int t0;
		for(int j=1;true;j++){
			s= vhod.readLine().trim().split(" ");
			n=Integer.parseInt(s[0]);
			m=Integer.parseInt(s[1]);
			if(n==0&&m==0){
				//System.out.println();
				break;
			}

			g= new Graf(n,m);
			for(int i=0;i<n;i++){
				g.dodajTocko();//pazit - oznake tock so za 1 manj!!
			}
			vr=new int[m];
			for(int i=0;i<m;i++){
				s=vhod.readLine().split(" ");
				//System.out.println(g.tocke.length);
				g.dodajPovezavo(g.tocke[Integer.parseInt(s[0])-1], g.tocke[Integer.parseInt(s[1])-1]);//oznake povezav so za eno manj!
				vr[i]=Integer.parseInt(s[2]);
			}
			//tu so podatki prebrani
			cas=dijkstra(g,vr,g.tocke[0]);
			
			/*for(int i=0;i<cas.length;i++){
				System.out.println(cas[i]);
			}*/
			
			//sedaj vemo, kdaj se posamezne kljucne domine podrejo.
			resitev = new int[3];//med katerima kljucnima dominama in kdaj se podre zadnja domina
			resitev[0]=-1;
			resitev[1]=-1;//zacetna to?ka je namrec 1 in se podre sama! - v casu 0
			resitev[2]=0;
			for(int i=0;i<m;i++){
				t0=Math.abs(cas[g.povezave[i].konec.nasprotna.oznaka]-cas[g.povezave[i].zacetek.nasprotna.oznaka]);//V kolikem casovnem intervalu padeta sosednji domini
				
				t=cas[g.povezave[i].konec.nasprotna.oznaka]+cas[g.povezave[i].zacetek.nasprotna.oznaka]+vr[i];//dvakratni cas, ki potece, da pade povezava (po krajsem racunu) - dvakratni zato, da lahko delamo s celinmi stevili
				if(t>=resitev[2]){//Tu se alternativa - lahko >=! TODO
					if(t0==vr[i]){//ce se pred podrtjem  enega izmed krajisc podre cela povezava - konec je v kljucni domini
						resitev[0]=resitev[1]=-1-((cas[g.povezave[i].konec.nasprotna.oznaka]>cas[g.povezave[i].zacetek.nasprotna.oznaka])? g.povezave[i].konec.nasprotna.oznaka : g.povezave[i].zacetek.nasprotna.oznaka);// z minus smo ozna?ili zato, da bomo vedeli, da je konec v vozliš?u!
						resitev[2]=t;
						continue;
					}
					if(t==resitev[2])continue;//ta if je le zaradi morebitne muhavosti serverja UVa
					
					//naslednji if je le zato, da bosta tocki urejeni po casu narascajoce, nato po indeksu. Verjetno ni potreben.
					if(cas[g.povezave[i].konec.nasprotna.oznaka]<cas[g.povezave[i].zacetek.nasprotna.oznaka]||(cas[g.povezave[i].konec.nasprotna.oznaka]==cas[g.povezave[i].zacetek.nasprotna.oznaka])&&g.povezave[i].konec.nasprotna.oznaka<g.povezave[i].zacetek.nasprotna.oznaka){
						resitev[0]=1+g.povezave[i].konec.nasprotna.oznaka;
						resitev[1]=1+g.povezave[i].zacetek.nasprotna.oznaka;
					}
					else{
						resitev[1]=1+g.povezave[i].konec.nasprotna.oznaka;
						resitev[0]=1+g.povezave[i].zacetek.nasprotna.oznaka;
					}
					resitev[2]=t;
				}
			}

			//sedaj moramo samo se izpisati resitev
			System.out.println("System #"+j);
			//g.izpis();
			System.out.println("The last domino falls after "+resitev[2]/2+"."+5*(resitev[2]%2)+ " seconds, "+(resitev[0]<=0? "at key domino "+(-resitev[0])+"." : "between key dominoes "+resitev[0]+" and "+resitev[1]+"."));
			System.out.println();

		}
	}

	public static int[] dijkstra(Graf g, int[] vr, Tocka t)
   {
      boolean[] obisk = new boolean[g.n];
      Povezava[] min = new Povezava[g.n];//minimalne povezave do povezanega dela
      //Povezava[] drevo = new Povezava[g.n];//koncne povezave - tega ne rabimo*********
      int[] vrednosti = new int[g.n];//kdaj bo katera izmed kljucnih domin padla

      obisk[t.oznaka] = true;
      vrednosti[t.oznaka] = 0;
      //drevo[t.oznaka] = null;  //gre ven*************************

      Tocka u,v;
      Povezava e;
      for (Stik s = t.sosedje; s != null; s = s.naslednji) {
         v = s.nasprotna;
         if(v==t)continue;
         e = s.povezava;
         min[v.oznaka] = e;//////preglej!
         //Tu zbrisal pogoj: if (min[v.oznaka] == null || vr[e.oznaka] < vr[min[v.oznaka].oznaka])
      }// s tem smo oznacili minimalne povezave do povezanega dela (zacetne tocke)

      while (true) {
    	 e=null;
         //domina u bo v naslednjem koraku po povezavi e "podrla" domino v

         for (int i = 0; i < g.n; ++i) {//po vozliscih iscemo naslednjo povezavo med povezanim in nepovezanim delom
            if (obisk[i]) continue;
            if (min[i] == null) continue;
            if (e == null) e = min[i];
            else {
            	//j=nasprotna tocka od i povezave min[i]
            	//k=nasprotna tocka od i povezave e
               int j = (min[i].konec.nasprotna.oznaka == i) ? min[i].zacetek.nasprotna.oznaka : min[i].konec.nasprotna.oznaka;
               int k = (e.konec.nasprotna.oznaka == i) ? e.zacetek.nasprotna.oznaka : e.konec.nasprotna.oznaka;
               if (vrednosti[j] + vr[min[i].oznaka] < vrednosti[k] + vr[e.oznaka]) e = min[i];
            }
         }
         if (e == null) break;//tu zakljucimo z while zanko! Smo povezali vse!

         if (obisk[e.konec.nasprotna.oznaka]) {
            v = e.zacetek.nasprotna;
            u = e.konec.nasprotna;
         }
         else {
            v = e.konec.nasprotna;
            u = e.zacetek.nasprotna;
         }
         //do tod smo nasli, katera kljucna domina bo podrta naslednja: v (iz u)
         obisk[v.oznaka] = true;
         vrednosti[v.oznaka] = vrednosti[u.oznaka] + vr[e.oznaka];//kdaj bo podrta domina v
         //drevo[v.oznaka] = e;//************************************

         //sedaj na novo nastavimo tabelo "minimalnih poti" iz nepovezanega dela
         for (Stik s = v.sosedje; s != null; s = s.naslednji) {
            u = s.nasprotna;
            if(obisk[u.oznaka])continue;//to dodal!
            e = s.povezava;
            if (min[u.oznaka] == null) min[u.oznaka] = e;
            else {
            	//j=oznaka nasprotne tocke od u (t.j. od "nove" tocke, od katere smo prisli)
            	//k=oznaka tiste tocke iz povezanega dela, ki je bila od u do zdaj najmanj oddaljena.
            	//stara koda: int j = (e.konec.nasprotna.oznaka == u.oznaka) ? e.zacetek.nasprotna.oznaka : e.konec.nasprotna.oznaka;
            	int j=v.oznaka;
            	int k = (min[u.oznaka].konec.nasprotna.oznaka == u.oznaka) ? min[u.oznaka].zacetek.nasprotna.oznaka : min[u.oznaka].konec.nasprotna.oznaka;
            	if (vrednosti[j] + vr[e.oznaka] < vrednosti[k] + vr[min[u.oznaka].oznaka]) min[u.oznaka] = e;
            }
         }
      }
      //return drevo;
      return vrednosti;
   }

}

class Graf
{
   Tocka[] tocke;
   Povezava[] povezave;
   int n;        // stevilo tock
   int m;        // stevilo povezav

   public Graf(int maxn, int maxm)
   {
      tocke = new Tocka[maxn];
      povezave = new Povezava[maxm];
      n = 0;
      m = 0;
   }

   public Tocka dodajTocko()
   {
      tocke[n] = new Tocka(n);
      return tocke[n++];
   }

   public Povezava dodajPovezavo(Tocka z, Tocka k)
   {
      povezave[m] = new Povezava(z, k, m);
      return povezave[m++];
   }

   public void odstraniTocko(Tocka t)
   {
      while (t.sosedje != null) odstraniPovezavo(t.sosedje.povezava);
      if (t.oznaka < n - 1) {
         tocke[t.oznaka] = tocke[n - 1];
         tocke[t.oznaka].oznaka = t.oznaka;
      }
      tocke[--n] = null;
   }

   public void odstraniPovezavo(Povezava p)
   {
      Tocka z = p.konec.nasprotna;    // kazalec na zacetno tocko
      Tocka k = p.zacetek.nasprotna;  // kazalec na koncno tocko
      if (p.zacetek == z.sosedje) z.sosedje = p.zacetek.naslednji;
      else {
         Stik stevec = z.sosedje;
         while (stevec.naslednji != p.zacetek) stevec = stevec.naslednji;
         stevec.naslednji = p.zacetek.naslednji;
      }
      if (p.konec == k.sosedje) k.sosedje = p.konec.naslednji;
      else {
         Stik stevec = k.sosedje;
         while (stevec.naslednji != p.konec) stevec = stevec.naslednji;
         stevec.naslednji = p.konec.naslednji;
      }
      if (p.oznaka < m - 1) {
         povezave[p.oznaka] = povezave[m - 1];
         povezave[p.oznaka].oznaka = p.oznaka;
      }
      povezave[--m] = null;
   }

   public void izpis()       // izpise sosede vsake tocke
   {
      for (int i = 0; i < n; ++i) {
         System.out.print(i + ":");
         for (Stik s = tocke[i].sosedje; s != null; s = s.naslednji)
            System.out.print(" " + s.nasprotna.oznaka);
         System.out.println();
      }
   }

   public static Graf petersen(int n, int k)
   {
      Graf g = new Graf(2 * n, 3 * n);
      for (int i = 0; i < 2 * n; ++i) g.dodajTocko();
      for (int i = 0; i < n; ++i) {
         g.dodajPovezavo(g.tocke[i], g.tocke[n + i]);
         g.dodajPovezavo(g.tocke[i], g.tocke[(i + 1) % n]);
         g.dodajPovezavo(g.tocke[n + i], g.tocke[n + (i + k) % n]);
      }
      return g;
   }

   public Tocka[] pregledVSirino(Tocka t)
   {
      Tocka[] vrsta = new Tocka[n];
      boolean[] obiskana = new boolean[n];
      int i = 0;
      int j = 0;
      vrsta[i++] = t;
      obiskana[t.oznaka] = true;
      while (j < i) {
         t = vrsta[j++];
         for (Stik s = t.sosedje; s != null; s = s.naslednji) {
            Tocka u = s.nasprotna;
            if (!obiskana[u.oznaka]) {
               vrsta[i++] = u;
               obiskana[u.oznaka] = true;
            }
         }
      }
      return vrsta;
   }
}

class Tocka
{
   Stik sosedje;
   int oznaka;

   public Tocka(int i)
   {
      oznaka = i;
      sosedje = null;
   }

   public int stopnja()
   {
      int i = 0;
      for (Stik s = sosedje; s != null; s = s.naslednji) ++i;
      return i;
   }
}

class Povezava
{
   Stik zacetek;
   Stik konec;
   int oznaka;

   public Povezava(Tocka z, Tocka k, int i)
   {
      zacetek = new Stik(k,this);
      zacetek.naslednji = z.sosedje;
      z.sosedje = zacetek;
      konec = new Stik(z, this);
      konec.naslednji = k.sosedje;
      k.sosedje = konec;
      oznaka = i;
   }

   public String toString()
   {
      return konec.nasprotna.oznaka + ", " + zacetek.nasprotna.oznaka;
   }
}

class Stik
{
   Tocka nasprotna;
   Povezava povezava;
   Stik naslednji;

   public Stik(Tocka t, Povezava p)
   {
      nasprotna = t;
      povezava = p;
      naslednji = null;
   }
}

keviii
New poster
Posts: 1
Joined: Sun May 03, 2009 3:29 pm

Re: 318 Domino Effect

Post by keviii » Sun May 03, 2009 3:35 pm

I had tested many test cases

the answers were correct too,but online-judge gave me wrong answer...

can somebody helps me?

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int rt_c;
int row[501][501];
int d[501];
int S[501];

double row_time[501][501];/*time when each row down*/

void relax(int,int);
void down(int,int);
int find_min(int);

int main(){
    int n,m,N=1;
    int i,j,k,l;
    double Max;
    int ver;
    int key;
    int p1,p2;


    /*freopen("318.in","r",stdin);
    freopen("out.out","w",stdout);*/
    
    
    scanf("%d",&n);
    scanf("%d",&m);
    while(!(0==n&&0==m)){
        if(N>=2)
            printf("\n");
        rt_c=0;
        for(k=1;k<=n;k++){
            S[k] = 0;
            d[k] = -1;
            for(j=1;j<=n;j++){
                row[k][j] = -1;
                row_time[k][j] = -1;
            }
        }
        /*initial*/
        
        for(k=0;k<m;k++){
            scanf("%d",&i);
            scanf("%d",&j);
            scanf("%d",&row[i][j]);
            row[j][i] = row[i][j];
        }
        /*read input*/
        
        d[1] = 0; 
        for(i=1;i<=n;i++){
            k = find_min(n);
            if(S[k]!=1){
                S[k]=1;
                for(j=1;j<=n;j++){
                    if(row[k][j]!=(-1))
                        relax(k,j);
                }  
            }  
        }
        /*run Dijkstra's algorithm to get the time key domino down*/
        for(i=1;i<n;i++){
            for(j=i+1;j<=n;j++){
                if(row[i][j]>=0)
                    down(i,j);
            }
        }
        /*get the time each row down*/
        
        Max = -1;
        ver = 0; /*if ver = 0 output key domino*/
        for(i=1;i<=n;i++){
            if(d[i] > Max){
                key = i;
                Max=d[i];
            }
        }
        /*find max for key and row*/
        for(i=1;i<n;i++){
            for(j=i+1;j<=n;j++){
                if(row_time[i][j] > Max){
                    Max = row_time[i][j];
                    p1=i;
                    p2=j;
                    ver=1;    
                }    
            }
        }
        
        printf("System #%d\n",N);

        printf("The last domino falls after %.1lf seconds, ",Max);
        
        if(ver==0)
            printf("at key domino %d.\n",key);
        else
            printf("between key dominoes %d and %d.\n",p1,p2);

        
        scanf("%d",&n);
        scanf("%d",&m);
        N++;
    }
    return 0;
}
void relax(int u,int v){
    if (d[v]>d[u]+row[u][v] || d[v]==-1)
        d[v] = d[u] + row[u][v];
}
void down(int u,int v){
    int i,j;
    double tmp1,tmp2,tmp3;
    if(d[u] > d[v]){
        i = d[u]; 
        j = d[v];
    }else{
        i = d[v]; 
        j = d[u];    
    }
    if(i-j == row[u][v])
         row_time[u][v] = i;
    else{
        tmp1 = i-j;
        tmp2 = j;
        tmp3 = row[u][v];
        row_time[u][v] = (i+j+tmp3)/2;
    }
    rt_c++;
}
int find_min(int n){
    int i,min,min_i,co;
    co = 0;
    for(i=1;i<=n;i++){
       if(S[i]!=1 && d[i]!=(-1)){
           if(0 == co){
               co = 1;
               min = d[i];
               min_i = i; 
           }else{
               if(d[i]<min){
                   min = d[i];
                   min_i = i;     
               }     
           }     
       }
    }
    return min_i;
}
Last edited by keviii on Mon May 04, 2009 6:07 am, edited 1 time in total.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 318 Domino Effect

Post by suneast » Thu Jul 29, 2010 2:15 pm

for all people who got WA
just try this

Code: Select all

1 0
easy to know the right answer...
just modify your code ,and got AC :wink:

????????
New poster
Posts: 5
Joined: Mon Nov 11, 2013 7:00 pm

Re: 318 Domino Effect

Post by ???????? » Sun Dec 22, 2013 5:53 pm

:evil: getting wa again and again..what's wrong in my code??somebody pls help...

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define pb push_back
#define loop(i,a,b) for (i=a;i<=b;i++)
#define maxm 501

using namespace std;

long long color[maxm],timee[maxm],mark[maxm];
vector< long long > g[maxm],cost[maxm];

long long r,s,z;

void dfs(long long a)
{
    color[a]=1;
    long long m=g[a].size(),i;

    loop(i,0,m-1)
    {
        long long v=g[a][i];
        if (!color[v])
        {
            r=a;s=v;
            z=cost[a][i];

            timee[v]=timee[a]+z;
            dfs(v);
        }
        else mark[v]=1;
    }
}

int main()
{
    long long domino_numb,i,j,k,rows,m,n;
    long long casee=1;
    
    while(scanf("%lld%lld",&domino_numb,&rows)==2 && domino_numb)
    {
        loop(i,1,domino_numb) {color[i]=0;mark[i]=0;}

        long long domino_1,domino_2,t;

        while(rows--)
        {
            scanf("%lld%lld%lld",&domino_1,&domino_2,&t);

            g[domino_1].push_back(domino_2);
            g[domino_2].push_back(domino_1);

            cost[domino_2].pb(t);
            cost[domino_1].pb(t);
        }

        s=1;z=0;
        timee[1]=0;
        dfs(1);

        double falling_timee=timee[s];
        printf("System #%lld\n",casee++);

        if (mark[s])
        {
            falling_timee-=(z/2.0);

            if (r>s) {long long temp=r;r=s;s=temp;}
            printf("The last domino falls after %.1lf seconds, between key dominoes %lld and %lld.\n",falling_timee,r,s);
        }
        else

          printf("The last domino falls after %.1lf seconds, at key domino %lld.\n",falling_timee,s);

        loop(i,1,domino_numb) {g[i].clear();cost[i].clear();}
        puts("");
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 318 Domino Effect

Post by brianfry713 » Thu Jan 16, 2014 2:47 am

Input:

Code: Select all

3 3
1 2 5
1 3 10
2 3 5
0 0
AC Output:

Code: Select all

System #1
The last domino falls after 10.0 seconds, at key domino 3.

Check input and AC output for thousands of problems on uDebug!

BlackBeard
New poster
Posts: 18
Joined: Wed Dec 17, 2014 9:44 pm

Re: 318 - Domino Effect

Post by BlackBeard » Sat Nov 14, 2015 1:49 pm

My code is getting correct ans for all inputs in this forum but still WA. Please anybody help...

Code: Select all

#include<bits/stdc++.h>

#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define sc4(w,x,y,z) scanf("%d%d%d%d",&w,&x,&y,&z)
#define pr(x) printf("%d",x)
#define pr2(x,y) printf("%d %d",x,y)
#define pr3(x,y,z) printf("%d %d %d",x,y,z)
#define pr4(w,x,y,z) printf("%d %d %d %d",w,x,y,z)
#define prn(x) printf("%d\n",x)
#define prn2(x,y) printf("%d %d\n",x,y)
#define prn3(x,y,z) printf("%d %d %d\n",x,y,z)
#define prn4(w,x,y,z) printf("%d %d %d %d\n",w,x,y,z)
#define memc(x,y) memcpy(&x,&y,sizeof(x))
#define mems(x,y) memset(x,y,sizeof(x))
#define fli() freopen("in.txt","r",stdin)
#define flo() freopen("out.txt","w",stdout)
#define Rep(i,x,v) for(int i=x;i<v;i++)
#define Repe(i,x,v) for(int i=x;i<=v;i++)
#define rep(i,v) for(int i=0;i<v;i++)
#define repe(i,v) for(int i=0;i<=v;i++)
#define Repr(i,x,v) for(int i=x;v<i;i--)
#define Repre(i,x,v) for(int i=x;v<=i;i--)
#define repr(i,x) for(int i=x;0<i;i--)
#define repre(i,x) for(int i=x;0<=i;i--)
#define repv(i,x) for(auto i=x.begin();i!=x.end();i++)
#define reprv(i,x) for(auto i=x.rbegin();i!=x.rend();i++)
#define Repn(i,x,v) for(int i=x;i<v;i++,putchar('\n'))
#define repn(i,v) for(int i=0;i<v;i++,putchar('\n'))
#define bl putchar('\n')
#define PI acos(-1)
#define ign cin.ignore(100,'\n')
#define gcc getchar()
#define pcc putchar
#define si size
#define fi first
#define se second
#define pf push_front
#define pof pop_front
#define pb push_back
#define pbb pop_back
#define mk make_pair
#define ll long long
#define ull unsigned long long
#define flerr 0.00000001
#define oo (ll)9e18
#define inf INT_MAX
#define maxintarrsize 536870911
#define MAX 505
using namespace std;

int nodes,edges,w,ed[MAX][MAX],aa,bb;
double ans;
struct edge { int to; int length; };
vector<edge>graph[MAX];
vector<int>x,y;
ll min_distance[MAX];

void dijkstra(int source) {
    int where;
    fill_n(min_distance,MAX,LLONG_MAX);
    set< pair<long long,int> > active_vertices;
    min_distance[ source ] = 0;
    active_vertices.insert( {0,source} );

    while (!active_vertices.empty()) {
        where = active_vertices.begin()->second;
        active_vertices.erase( active_vertices.begin() );
        for (auto edge : graph[where]){
            if (min_distance[edge.to] > min_distance[where] + edge.length) {
                active_vertices.erase( { min_distance[edge.to], edge.to } );
                min_distance[edge.to] = min_distance[where] + edge.length;
                active_vertices.insert( { min_distance[edge.to], edge.to } );
            }
        }
    }
}

int main(){
//    fli();
    int u,v,ss,c=1;
    double tmp;
    ll d1,d2,dd;
    edge tt;
    bool flag;
    while(sc2(nodes,edges)==2,nodes or edges){
        printf("System #%d\n",c++);
        if(edges==0){
            printf("The last domino falls after 0.0 seconds, at key domino 1.\n\n");
            continue;
        }
        rep(i,edges){
            sc3(u,v,w);
            x.pb(u);
            y.pb(v);
            ed[u][v]=w;
            ed[v][u]=w;
            tt.to=v;tt.length=w;
            graph[u].pb(tt);
            tt.to=u;
            graph[v].pb(tt);
        }
        dijkstra(1);
        ans=0;
        ss=x.si();
        rep(i,ss){
            u=x[i];
            v=y[i];
            d1=min_distance[x[i]];
            d2=min_distance[y[i]];
            if(d1==LLONG_MAX or d2==LLONG_MAX) continue;
            if(d2>d1) swap(d1,d2),swap(u,v);
            dd=d1-d2;
            if(dd==ed[u][v]){
                if(dd*1.0>ans or (dd*1.0==ans and flag==false) or (dd*1.0==ans and flag==true and u<aa)){
                    ans=dd;
                    aa=u;
                    flag=true;
                }
            }
            else if(dd<ed[u][v]){
                tmp=d1 + ( (ed[u][v]-(d1-d2))/2.0 );
                if(tmp>ans){
                    ans=tmp;
                    aa=u;
                    bb=v;
                    if(aa>bb) swap(aa,bb);
                    flag=false;
                }
                else if(tmp==ans and flag==false){
                    if(u>v) swap(u,v);
                    if(u<aa){
                        ans=tmp;
                        aa=u;
                        bb=v;
                        flag=false;
                    }
                }
            }
        }
        if(flag){
            printf("The last domino falls after %.1f seconds, at key domino %d.\n\n",ans,aa);
        }
        else{
            printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n",ans,aa,bb);
        }
        Repe(i,1,nodes) graph[i].clear();
        x.clear();
        y.clear();
    }
    return 0;
}

Post Reply

Return to “Volume 3 (300-399)”