908 - Re-connecting Computer Sites

[Rc Tushar]

My code is Giving TLE . First two time i used vector and this time i used Priority queue bt all the same ... here is my code---

Code: Select all

#include<bits/stdc++.h>

#define pi 2*acos(0.0)
#define PS system("pause")
#define siter(n)  for(set<int>::iterator it=n.begin();it!=n.end();it++)
#define FOR(s,e,inc) for(int i=s;i<=e;i+=inc)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define Sfor(n) for(int i=1;i<=n;i++)
#define inf (1<<30)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define F first
#define S second
#define sz(x) ((int)x.size())
#define eps 1e-9
#define gcd(x,y) __gcd(x,y)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define on(x,w)  x=x|(1<<w)
#define check(x,w) (x&(1<<w))==(1<<w)?true:false
#define all(x) (x).begin(),(x).end()
#define s(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define pf printf
#define ll long long int
#define MOD 1000000007
#define sqr(x) (( (x)* (x))%MOD)
#define cube(x)   ( (sqr(x)*(x))%MOD)
#define bit_cnt(x)   __builtin_popcount(x)
#define INT(c)  ((int)((c) - '0'))
#define CHAR(i) ((char)(i + int('0')))
#define maxall(v) *max_element(all(v))
#define minall(v) *min_element(all(v))
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define btz(a)   __builtin_ctz(a)
#define Mems(p,n) memset(p, n, sizeof(p))
#define makeint(n,s)  istringstream(s)>>n
#define BOUNDARY(i,j,Row,Col) ((i >= 0 && i < Row) && (j >= 0 && j < Col))
#define M  1000009
using namespace std;

//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};                         //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};     //8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};   //Knight Direction
//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1};              //Hexagonal Direction

typedef vector<int> vi;

template<class T>
inline bool fs(T &x)
{
    int c=getchar();
    int sgn=1;
    while(~c&&c<'0'||c>'9')
    {
        if(c=='-')sgn=-1;
        c=getchar();
    }
    for(x=0; ~c&&'0'<=c&&c<='9'; c=getchar())
        x=x*10+c-'0';
        x*=sgn;
    return ~c;
}

//~~~~~~~~~~~~~~~~~CODE STARTING POINT~~~~~~~~~~~~~~~~~~~~~~

struct st
{
    int u,v,w;
    st (int a,int b,int c)
    {
        u=a;
        v=b;
        w=c;
    }
    bool operator <(const st &p)const
    {
        return w>p.w;
    }
};

int par[M];

int rep(int n)
{
    if(par[n]==n)
        return n;
    else
        return par[n]=rep(par[n]);
}

int mst(int n,priority_queue<st> q)
{
    ll cnt=0,sum=0;
    int u,v;

    for(int i=1;i<=n;i++)
    par[i]=i;

    while(!q.empty())
    {
        st top=q.top();
        q.pop();
        u=rep(top.u);
        v=rep(top.v);
        if(u!=v)
        {
            cnt++;
            sum+=top.w;
            par[u]=v;
            if(cnt==n-1)
                break;
        }
    }
    return sum;
}

int main()
{
int n,m,a,b,c,k;
while(true)
{
    priority_queue<st> B;
    ll sum=0;
    s(n);
    loop(i,1,n)
    {
        s(a);
        s(b);
        s(c);
        sum+=c;
    }
    s(k);
    loop(i,0,k)
    {
        s(a);
        s(b);
        s(c);
        B.push(st(a,b,c));
    }

    s(m);
    loop(i,0,m)
    {
        s(a);
        s(b);
        s(c);
        B.push(st(a,b,c));
    }
    cout<<sum<<endl;
    cout<<mst(n,B)<<"\n\n";
}

return 0;
}

[brianfry713]

Your code never terminates.
I used:
while(scanf("%d", &N) == 1) {

[Rc Tushar]

how could i missed that thing !! by the way thnx a lot

[garbage]

Code: Select all

Thnx brianfry713,
Got Accepted

[brianfry713]

Are you clearing vec between test cases?

[jporcelli1120]

Any one help out alittle why WA? Thanks guys

Code: Select all

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

#define PI acos(-1)
#define sqr(x) ((x) * (x))
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) (int)(c).size()
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPD(i, a, b) for (int i = int(a); i >= int(b); i--)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef map<int,int> mii;
typedef set<int> si;

class DSU {
private:
	vi pset; 
public:
	void initSet(int _size) { pset.clear(); pset.resize(_size); REP (i, 0, _size - 1) pset[i] = i; }
	int findSet(int i) { return (pset[i] == i) ? i : (pset[i] = findSet(pset[i])); }
	void unionSet(int i, int j) { pset[findSet(i)] = findSet(j); }
	bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
};

const int MAXN=1000000;

vector< pair<int, ii> > edgeList;
//PQ default: sort descending. To sort ascending, we can use <(negative) weight(i, j), <i, j> >
DSU t;

int V;
ll mst_cost;

//For each edge with (i, j, weight) format -  edgeList.push(make_pair(-weight, make_pair(i, j)));
//Alternative implementation: use STL vector and algorithm:sort
void mst() {
	sort(ALL(edgeList));
	mst_cost = 0; t.initSet(V); // all V are disjoint sets initially, see Section 2.3.2 (CP1)
	while (!edgeList.empty()) { // while there exist more edges, O(E)
		pair<int, ii> front = edgeList.front(); edgeList.erase(edgeList.begin());
		if (!t.isSameSet(front.second.first, front.second.second)) { // if no cycle
			mst_cost += front.first; 
			t.unionSet(front.second.first, front.second.second); // link these two vertices
		} 
	}
	// note that the number of disjoint sets must eventually be one!
	// otherwise, no MST has been formed...	
}

#define PROD //clocking off
int main() {
#ifndef PROD
clock_t stop_s,start_s;
start_s=clock();
#endif
	
	int N, K, M, x, y, c;
	ll pc;

	while(cin >> N) {
		V=N+1; pc=0;
		edgeList.clear();

		REP(i, 1, N-1) { 
			cin >> x >> y >> c; 
			pc+=c; 
		}

		cin >> K;
		REP(i, 1, K) {
			cin >> x >> y >> c;
			edgeList.PB(MP(c, ii(x,y)));
		}

		cin >> M;
		REP(i, 1, M) {
			cin >> x >> y >> c;
			edgeList.PB(MP(c, ii(x,y)));
		}

		mst();

		cout << pc << "\n" << mst_cost << endl;
		if(!cin.eof()) { cout << "\n"; }
	}


#ifndef PROD
stop_s=clock();
cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
#endif
	return 0;
}

[facug91]

It could be because you initialize the Union Find Disjoint Set from 0 to n-1, but then the nodes are index from 1 to n.