oj.uz

Submission #133207

# Submission time Handle Problem Language Result Execution time Memory
133207 2019-07-20T09:17:42 Z rajarshi_basu Bridges (APIO19_bridges) C++14
0 / 100
 3000 ms 10344 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
#define vv vector
 
using namespace std;

const int MAXN = 50*1000+1;
const int MAXM = 2*MAXN;
int n;
struct DSU{
	int parent[MAXN];
	int sz[MAXN];
	int rnk[MAXN];
	void init(){
		FOR(i,n)parent[i] = i;
		FOR(i,n)sz[i] = 1;
		FOR(i,n)rnk[i] = 1;
	}
	inline int find(int a){
		if(a == parent[a])return a;
		return find(parent[a]);
	}
	inline void merge(int a,int b){
		if(isSame(a,b))return;
		int pa = find(a);
		int pb = find(b);
		sz[pa] += sz[pb];
		parent[pb] = pa;
	}
	int getSize(int a){
		return sz[find(a)];
	}
	bool isSame(int a,int b){
		return find(a) == find(b);
	}
};

struct edge{
	int ID;
	int a,b;
	int w;
	edge(int id,int aa,int bb,int ww){
		ID = id;
		a = aa;
		b = bb;
		w = ww;
	}
};
struct query{
	int type; // 1 is update, 2 is query
	int tm;
	int info1; // node for query, edge for update
	int info2; // value for either
	int id;
	query(int t,int a,int b,int c){
		type = t;
		tm = id = a;
		info1 = b;
		info2 = c;

	}
};

int finalANS[MAXM];
vv<edge> allEdges;

vi rem;
bool edg[MAXM];

void processQueries(vv<query> allQueries){
	FOR(i,MAXM)edg[i] = 0;
	for(auto e : allQueries){
		if(e.type == 1){
			edg[e.info1] = 1;
			rem.pb(e.info1);
		}
	}
	//cout << "REM CONTENTS : " ;
	//for(auto e : rem)cout << e << " ";cout << endl;
	//DSU dsu;
	//dsu.init();

	vv<query> actualQueries;
	for(auto e : allQueries){
		if(e.type == 2){
			actualQueries.pb(e);
		}
	}

	sort(actualQueries.begin(), actualQueries.end(), [&](query a,query b){
		return a.info2 >= b.info2;
	});

	for(auto q : actualQueries){
		//cout << "PROCESSING FOR QUERY : " << q.info1 << " " << q.info2 << endl;
		DSU dsu;
		dsu.init();
		FOR(i,allEdges.size()){
			if(edg[i])continue;
			if(allEdges[i].w < q.info2)continue;
			//cout << "PERMEDGE PROCESSED : " << i+1 << endl;
			dsu.merge(allEdges[i].a,allEdges[i].b);
		}
		map<int,int> mp;
		for(auto xx : rem){
			mp[xx] = allEdges[xx].w;
		}
		for(auto e : allQueries){
			if(e.type == 2)continue;
			if(e.tm > q.tm)continue;

			//cout << "BLOCK EDGE SEEN : " << e.info1+1 << " " << e.info2 << endl;
			mp[e.info1] = e.info2;
		}
		for(auto x : mp){

			
			if(x.ss >= q.info2){
				//cout << "BLOCK EDGE SEEN : " << x.ff+1 << " " << x.ss << endl;				
				dsu.merge(allEdges[x.ff].a,allEdges[x.ff].b);
			}
		}
		finalANS[q.id] = dsu.getSize(q.info1);
	}

	for(auto e : allQueries){
		if(e.type == 1){
			allEdges[e.info1].w = e.info2;
		}
	}
}
bool quer[MAXM];

int main(){
	int m;
	cin >> n >> m;
	FOR(i,m){
		int a,b,c;
		cin >> a >> b >> c;
		a--;b--;
		allEdges.pb(edge(i,a,b,c));
	}
	int q;
	cin >> q;
	FOR(i,MAXM)finalANS[i] = -1;
	int BLOCK = 100000;
	vv<query> allq;

	FOR(i,q){
		int a,b,c;
		cin >> a >> b >> c;
		if(a == 2)quer[i] = 1;
		b--;
		allq.pb(query(a,i,b,c));
		if((i+1)%BLOCK == 0){
			processQueries(allq);
			allq.clear();
		}
	}
	if(allq.size() > 0)processQueries(allq);
	FOR(i,q){
		if(quer[i])cout << finalANS[i] << endl;
	}
	return 0;
}

Compilation message

bridges.cpp: In function 'void processQueries(std::vector<query>)':
bridges.cpp:19:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
bridges.cpp:128:7:
   FOR(i,allEdges.size()){
       ~~~~~~~~~~~~~~~~~        
bridges.cpp:128:3: note: in expansion of macro 'FOR'
   FOR(i,allEdges.size()){
   ^~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Execution timed out 3046 ms 1468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3015 ms 8820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 8104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 10344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3015 ms 8820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Execution timed out 3046 ms 1468 KB Time limit exceeded
4 Halted 0 ms 0 KB -