Cod sursa(job #2267404)

Utilizator divianegoescuDivia Negoescu divianegoescu Data 23 octombrie 2018 16:58:58
Problema Oz Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <stdio.h>
FILE *fin=fopen("oz.in","r");
using namespace std;
ofstream fout("oz.out");
int n,m,i,j,t;
unsigned long long  v[10001],d,r,x,aux;
struct ijd
{
    int I;
    int J;
    unsigned long long D;
}w[100001];
int cmmdc(unsigned long long a,unsigned long long d)
{
    x=a;
    r=d;
    while(r!=0)
    {
        aux=x;
        x=r;
        r=aux%r;
    }
    return x;
}
int main()
{
    fscanf(fin,"%d%d",&n,&m);
    if(m<n/2)
    {
        fout<<"-1";
        return 0;
    }
    for(i=1;i<=n;i++)
        v[i]=1;
    for(t=1;t<=m;t++)
    {
        fscanf(fin,"%d%d%d",&i,&j,&d);
        w[t].I=i;
        w[t].J=j;
        w[t].D=d;
        aux=cmmdc(v[i],d);
        v[i]=(v[i]*d)/aux;
        aux=cmmdc(v[j],d);
        v[j]=(v[j]*d)/aux;
        if(v[i]>2000000000 || v[j]>2000000000){fout<<"-1";return 0;}
    }
    for(t=1;t<=m;t++)
    {

        aux=cmmdc(v[w[t].I],v[w[t].J]);
        if(w[t].D != aux){fout<<"-1";return 0;}
    }
    for(t=1;t<=n;t++)
        fout<<v[t]<<" ";
    return 0;
}