oj.uz

Submission #130984

# Submission time Handle Problem Language Result Execution time Memory
130984 2019-07-16T11:02:25 Z claudy Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 19936 KB 
//# 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];
int viz[1 << 17];
vector<int>qry[1 << 17];
int used[1 << 17];

const int L = 50005;


int find(int x)
{
	if(x == p[x]) return x;
	return p[x] = find(p[x]);
}

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];
	}
	set<pair<int,int>>st;
	for(int i = 1;i <= m;i++)
	{
		st.insert(mp(-d[i],i));
	}
	st.insert(mp(0,0));
	for(int i = 0;i < q;i += L)
	{
		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)
			{
				auto it = st.find(mp(-d[b[j]],b[j]));
				if(it != st.end()) st.erase(it);
			}
		}
		for(int j = i;j < min(q,i + L);j++)
		{
			if(a[j] == 2)
			{
				auto it = st.upper_bound(mp(-c[j],2e9));
				qry[(*it).second].pb(j);
			}
		}
		for(auto IT : st)
		{
			int idx = IT.second;
			for(auto it : qry[idx])
			{
				vector<int>temp;
				vector<int>kek;
				for(int j = it - 1;j >= i;j--)
				{
					if(a[j] == 1 && !used[b[j]])
					{
						used[b[j]] = 1;
						kek.pb(b[j]);
						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);
								viz[x] = viz[y] = 0;
								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;
						kek.pb(b[j]);
						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);
								viz[x] = viz[y] = 0;
								temp.pb(x);
								temp.pb(y);
							}
						}
					}
				}
				ans[it] = dfs(find(b[it]));
				for(auto itit : kek) used[itit] = 0;
				kek.clear();
				while(sz(temp))
				{
					vec[temp.back()].clear();
					temp.pop_back();
				}				
			}
			if(idx) unite(u[idx],v[idx]);
		}
		vector<int>kek;
		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;
				kek.pb(b[j]);
				st.insert(mp(-d[b[j]],b[j]));
			}
		}
		for(auto it : kek) used[it] = 0;
	}
	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 6492 KB Output is correct
2 Correct 8 ms 6520 KB Output is correct
3 Correct 455 ms 7032 KB Output is correct
4 Correct 97 ms 7036 KB Output is correct
5 Correct 273 ms 6904 KB Output is correct
6 Correct 265 ms 6904 KB Output is correct
7 Correct 288 ms 7032 KB Output is correct
8 Correct 269 ms 7036 KB Output is correct
9 Correct 280 ms 7032 KB Output is correct
10 Correct 269 ms 7032 KB Output is correct
11 Correct 268 ms 7092 KB Output is correct
12 Correct 265 ms 6904 KB Output is correct
13 Correct 287 ms 7032 KB Output is correct
14 Correct 288 ms 7032 KB Output is correct
15 Correct 294 ms 6904 KB Output is correct
16 Correct 272 ms 6904 KB Output is correct
17 Correct 287 ms 6928 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3090 ms 15028 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 3006 ms 13148 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 3036 ms 19936 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 3090 ms 15028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6492 KB Output is correct
2 Correct 8 ms 6520 KB Output is correct
3 Correct 455 ms 7032 KB Output is correct
4 Correct 97 ms 7036 KB Output is correct
5 Correct 273 ms 6904 KB Output is correct
6 Correct 265 ms 6904 KB Output is correct
7 Correct 288 ms 7032 KB Output is correct
8 Correct 269 ms 7036 KB Output is correct
9 Correct 280 ms 7032 KB Output is correct
10 Correct 269 ms 7032 KB Output is correct
11 Correct 268 ms 7092 KB Output is correct
12 Correct 265 ms 6904 KB Output is correct
13 Correct 287 ms 7032 KB Output is correct
14 Correct 288 ms 7032 KB Output is correct
15 Correct 294 ms 6904 KB Output is correct
16 Correct 272 ms 6904 KB Output is correct
17 Correct 287 ms 6928 KB Output is correct
18 Execution timed out 3090 ms 15028 KB Time limit exceeded
19 Halted 0 ms 0 KB -