oj.uz

Submission #133145

# Submission time Handle Problem Language Result Execution time Memory
133145 2019-07-20T07:57:04 Z rajarshi_basu Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 4068 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;

struct DSU{
	int parent[MAXN];
	int sz[MAXN];
	int rnk[MAXN];
	void init(){
		FOR(i,MAXN)parent[i] = i;
		FOR(i,MAXN)sz[i] = 1;
		FOR(i,MAXN)rnk[i] = 1;
	}
	int find(int a){
		if(a == parent[a])return a;
		return find(parent[a]);
	}
	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 n,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 = 1;
	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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 2489 ms 1512 KB Output is correct
4 Correct 1056 ms 1384 KB Output is correct
5 Correct 1338 ms 1556 KB Output is correct
6 Correct 1318 ms 1564 KB Output is correct
7 Correct 1367 ms 1440 KB Output is correct
8 Correct 1380 ms 1536 KB Output is correct
9 Correct 1342 ms 1528 KB Output is correct
10 Correct 1342 ms 1564 KB Output is correct
11 Correct 1340 ms 1656 KB Output is correct
12 Correct 1338 ms 1528 KB Output is correct
13 Correct 1458 ms 1688 KB Output is correct
14 Correct 1439 ms 1528 KB Output is correct
15 Correct 1361 ms 1656 KB Output is correct
16 Correct 1350 ms 1592 KB Output is correct
17 Correct 1354 ms 1544 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 3628 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 3043 ms 3192 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 3031 ms 4068 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 3043 ms 3628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 2489 ms 1512 KB Output is correct
4 Correct 1056 ms 1384 KB Output is correct
5 Correct 1338 ms 1556 KB Output is correct
6 Correct 1318 ms 1564 KB Output is correct
7 Correct 1367 ms 1440 KB Output is correct
8 Correct 1380 ms 1536 KB Output is correct
9 Correct 1342 ms 1528 KB Output is correct
10 Correct 1342 ms 1564 KB Output is correct
11 Correct 1340 ms 1656 KB Output is correct
12 Correct 1338 ms 1528 KB Output is correct
13 Correct 1458 ms 1688 KB Output is correct
14 Correct 1439 ms 1528 KB Output is correct
15 Correct 1361 ms 1656 KB Output is correct
16 Correct 1350 ms 1592 KB Output is correct
17 Correct 1354 ms 1544 KB Output is correct
18 Execution timed out 3043 ms 3628 KB Time limit exceeded
19 Halted 0 ms 0 KB -