Submission #131053

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
131053	2019-07-16T11:59:48 Z	claudy	Bridges (APIO19_bridges)	C++14	44 / 100	3000 ms	13944 KB

bridges

# pragma GCC optimize("Ofast,no-stack-protector")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;
 
/*
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
Tree<int>tr;
*/
 
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# define LOCAL
# define sim template < class c
# define ris return * this
# define dor > debug & operator <<
# define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int gcd(int a, int b)
{
if(b) return gcd(b,a%b);
return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
int n,m,u[1 << 17],v[1 << 17],d[1 << 17],a[1 << 17],b[1 << 17],c[1 << 17],q,sze[1 << 17],p[1 << 17],ans[1 << 17];
vector<int>vec[1 << 17];
vector<int>qry[1 << 17];
bitset<100005>used,viz,afk;

const int L = 1000;
 
 
inline int find(int x)
{
	if(x == p[x]) return x;
	return p[x] = find(p[x]);
}
 
inline void unite(int a,int b)
{
	a = find(a);
	b = find(b);
	if(a != b)
	{
		if(sze[a] > sze[b]) swap(a,b);
		p[a] = b;
		sze[b] += sze[a];
	}
}
 
int dfs(int nod)
{
	viz[nod] = 1;
	int x = sze[nod];
	for(auto it : vec[nod])
	{
		if(!viz[it]) x += dfs(it);
	}
	return x;
}
 
int32_t main(){_
	//freopen("input","r",stdin);
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		cin >> u[i] >> v[i] >> d[i];
	}
	cin >> q;
	for(int i = 0;i < q;i++)
	{
		cin >> a[i] >> b[i] >> c[i];
	}
	vector<pair<int,int>>st;
	for(int i = 1;i <= m;i++)
	{
		st.pb(mp(-d[i],i));
	}
	st.pb(mp(0,0));
	for(int i = 0;i < q;i += L)
	{
		sort(st.begin(),st.end());
		for(int j = 1;j <= n;j++) p[j] = j,sze[j] = 1;
		for(int j = 0;j <= m;j++) qry[j].clear();
		for(int j = i;j < min(q,i + L);j++)
		{
			if(a[j] == 1)
			{
				afk[b[j]] = 1;
			}
		}
		for(int j = i;j < min(q,i + L);j++)
		{
			if(a[j] == 2)
			{
				auto it = upper_bound(st.begin(),st.end(),mp(-c[j],2000000000));
				qry[(*it).second].pb(j);
			}
		}
		vector<pair<int,int>>myvec;
		for(auto IT : st)
		{
			int idx = IT.second;
			for(auto it : qry[idx])
			{
				vector<int>temp;
				vector<int>kek;
				used.reset();viz.reset();
				for(int j = it - 1;j >= i;--j)
				{
					if(a[j] == 1 && !used[b[j]])
					{
						used[b[j]] = 1;
						if(c[j] >= c[it])
						{
							int x = find(u[b[j]]);
							int y = find(v[b[j]]);
							if(x != y)
							{
								vec[x].push_back(y);
								vec[y].push_back(x);
								temp.pb(x);
								temp.pb(y);
							}
						}
					}
				}
				for(int j = it + 1;j < min(q,i + L);++j)
				{
					if(a[j] == 1 && !used[b[j]])
					{
						used[b[j]] = 1;
						if(d[b[j]] >= c[it])
						{
							int x = find(u[b[j]]);
							int y = find(v[b[j]]);
							if(x != y)
							{
								vec[x].pb(y);
								vec[y].pb(x);
								temp.pb(x);
								temp.pb(y);
							}
						}
					}
				}
				ans[it] = dfs(find(b[it]));
				for(auto itit : temp) vec[itit].clear();		
			}
			if(!afk[idx])
			{
				if(idx) unite(u[idx],v[idx]);
				myvec.pb(IT);
			}
		}
		used.reset();
		for(int j = min(q,i + L - 1);j >= i;j--)
		{
			if(a[j] == 1 && !used[b[j]])
			{
				d[b[j]] = c[j];
				used[b[j]] = 1;
				afk[b[j]] = 0;
				myvec.pb(mp(-d[b[j]],b[j]));
			}
		}
		st = myvec;
	}
	for(int i = 0;i < q;i++)
	{
		if(a[i] == 2) 
		{
			cout << max(1,ans[i]) << '\n';
		}
	}
	return 0;
}
 
 
 
 
 

Compilation message

bridges.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	6524 KB	Output is correct
2	Correct	8 ms	6492 KB	Output is correct
3	Correct	74 ms	6804 KB	Output is correct
4	Correct	27 ms	6776 KB	Output is correct
5	Correct	48 ms	6776 KB	Output is correct
6	Correct	44 ms	6696 KB	Output is correct
7	Correct	49 ms	6756 KB	Output is correct
8	Correct	49 ms	6808 KB	Output is correct
9	Correct	54 ms	6752 KB	Output is correct
10	Correct	49 ms	6776 KB	Output is correct
11	Correct	48 ms	6788 KB	Output is correct
12	Correct	52 ms	6776 KB	Output is correct
13	Correct	59 ms	6776 KB	Output is correct
14	Correct	55 ms	6748 KB	Output is correct
15	Correct	54 ms	6768 KB	Output is correct
16	Correct	48 ms	6776 KB	Output is correct
17	Correct	48 ms	6776 KB	Output is correct

Subtask #2

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2437 ms	12652 KB	Output is correct
2	Correct	2388 ms	12644 KB	Output is correct
3	Correct	2417 ms	12672 KB	Output is correct
4	Correct	2345 ms	12692 KB	Output is correct
5	Correct	2345 ms	12732 KB	Output is correct
6	Execution timed out	3008 ms	10668 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2048 ms	11384 KB	Output is correct
2	Correct	1704 ms	9268 KB	Output is correct
3	Correct	2532 ms	11176 KB	Output is correct
4	Correct	2047 ms	11332 KB	Output is correct
5	Correct	174 ms	8336 KB	Output is correct
6	Correct	2265 ms	11084 KB	Output is correct
7	Correct	1865 ms	11276 KB	Output is correct
8	Correct	1595 ms	11180 KB	Output is correct
9	Correct	1317 ms	10616 KB	Output is correct
10	Correct	1195 ms	10808 KB	Output is correct
11	Correct	1318 ms	10924 KB	Output is correct
12	Correct	1112 ms	10992 KB	Output is correct

Subtask #4

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1458 ms	13908 KB	Output is correct
2	Correct	178 ms	8368 KB	Output is correct
3	Correct	163 ms	10748 KB	Output is correct
4	Correct	127 ms	10516 KB	Output is correct
5	Correct	1223 ms	12348 KB	Output is correct
6	Correct	1424 ms	13864 KB	Output is correct
7	Correct	1192 ms	12368 KB	Output is correct
8	Correct	903 ms	11596 KB	Output is correct
9	Correct	895 ms	11484 KB	Output is correct
10	Correct	844 ms	10612 KB	Output is correct
11	Correct	1291 ms	13064 KB	Output is correct
12	Correct	1267 ms	13004 KB	Output is correct
13	Correct	1229 ms	11860 KB	Output is correct
14	Correct	1148 ms	12472 KB	Output is correct
15	Correct	1186 ms	12324 KB	Output is correct
16	Correct	1563 ms	13816 KB	Output is correct
17	Correct	1505 ms	13824 KB	Output is correct
18	Correct	1585 ms	13944 KB	Output is correct
19	Correct	1514 ms	13928 KB	Output is correct
20	Correct	1406 ms	11988 KB	Output is correct
21	Correct	1377 ms	12168 KB	Output is correct
22	Correct	1461 ms	12940 KB	Output is correct
23	Correct	1214 ms	11744 KB	Output is correct

Subtask #5

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2437 ms	12652 KB	Output is correct
2	Correct	2388 ms	12644 KB	Output is correct
3	Correct	2417 ms	12672 KB	Output is correct
4	Correct	2345 ms	12692 KB	Output is correct
5	Correct	2345 ms	12732 KB	Output is correct
6	Execution timed out	3008 ms	10668 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #6

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	6524 KB	Output is correct
2	Correct	8 ms	6492 KB	Output is correct
3	Correct	74 ms	6804 KB	Output is correct
4	Correct	27 ms	6776 KB	Output is correct
5	Correct	48 ms	6776 KB	Output is correct
6	Correct	44 ms	6696 KB	Output is correct
7	Correct	49 ms	6756 KB	Output is correct
8	Correct	49 ms	6808 KB	Output is correct
9	Correct	54 ms	6752 KB	Output is correct
10	Correct	49 ms	6776 KB	Output is correct
11	Correct	48 ms	6788 KB	Output is correct
12	Correct	52 ms	6776 KB	Output is correct
13	Correct	59 ms	6776 KB	Output is correct
14	Correct	55 ms	6748 KB	Output is correct
15	Correct	54 ms	6768 KB	Output is correct
16	Correct	48 ms	6776 KB	Output is correct
17	Correct	48 ms	6776 KB	Output is correct
18	Correct	2437 ms	12652 KB	Output is correct
19	Correct	2388 ms	12644 KB	Output is correct
20	Correct	2417 ms	12672 KB	Output is correct
21	Correct	2345 ms	12692 KB	Output is correct
22	Correct	2345 ms	12732 KB	Output is correct
23	Execution timed out	3008 ms	10668 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-