oj.uz

Submission #927301

# Submission time Handle Problem Language Result Execution time Memory
927301 2024-02-14T16:51:47 Z Dzadzo Bridges (APIO19_bridges) C++17
16 / 100
 3000 ms 433656 KB 
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 100000
using namespace std;
int p[MAXN+1];
int s[MAXN+1];
stack <pair<pii,int>> st;
int find(int v){
	if (p[v]==v)return v;
	return find(p[v]);
}
void unite(int v,int u){
	v=find(v);
	u=find(u);
	if (s[u]>s[v])swap(u,v);
	st.push({{u,v},p[u]});
	p[u]=v;
	s[v]+=s[u];
}
void rollback(){
	int u=st.top().F.F;
	int v=st.top().F.S;
	int pu=st.top().S;
	p[u]=pu;
	s[v]-=s[u];
	st.pop();
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	vector<pair<pii,pii>> edges;
	int V[m+1],U[m+1],W[m+1];
	for (int i=1;i<=m;i++){
		cin>>U[i]>>V[i]>>W[i];
		edges.pb({{W[i],i},{U[i],V[i]}});
	}
	sort(edges.rbegin(),edges.rend());
	edges.pb({{0,0},{0,0}});
	int q;
	cin>>q;
	int B=sqrt(q)+1;
	vp temp[q+1];
	vector<pair<pii,int>> Q;
	int cur=0;
	vi res(q+1);
	vb marked(m+2);
	for (int tt=1;tt<=q;tt++){
		int tp,x,y;
		cin>>tp>>x>>y;
		temp[tt]=temp[tt-1];
		if (tp==1){
			temp[tt].pb({x,y});
		}else{
			Q.pb({{y,x},tt});
		}
		cur++;
		if (cur==B || tt==q){
			Q.pb({{0,0},0});
			sort(Q.rbegin(),Q.rend());
			int l=0;
			for (auto &[id,c]:temp[tt])marked[id]=true;
			while (st.size())st.pop();
			for (int i=1;i<=n;i++)s[i]=1,p[i]=i;
			for (auto z:edges){
				int w=z.F.F;
				int ind=z.F.S;
				int u=z.S.F;
				int v=z.S.S;
				if (marked[ind])continue;
				while (w<Q[l].F.F){
					int cnt=0;
					for (auto k:temp[Q[l].S]){
						marked[k.F]=false;
						if (k.S>=Q[l].F.F && find(U[k.F])!=find(V[k.F]))unite(U[k.F],V[k.F]),cnt++;
					}
					for (auto k:temp[tt]){
						if (!marked[k.F])continue;
						if (W[k.F]>=Q[l].F.F &&find(U[k.F])!=find(V[k.F]))unite(U[k.F],V[k.F]),cnt++;						
					}
					for (auto k:temp[Q[l].S])marked[k.F]=true;					
					res[Q[l].S]=s[find(Q[l].F.S)];
					while (cnt--)rollback();
					l++;
				}
				if (find(u)!=find(v))unite(u,v);
			}
			Q.clear();
			for (auto [id,c]:temp[tt]){
				marked[id]=false;
				W[id]=c;
			}
			edges.clear();
			for (int i=1;i<=m;i++)edges.pb({{W[i],i},{U[i],V[i]}});
			sort(edges.rbegin(),edges.rend());edges.pb({{0,0},{0,0}});
			for (int i=tt-cur+1;i<=tt;i++)temp[i].clear();
			cur=0;
		}
	}
	for (int i=1;i<=q;i++)if (res[i])cout<<res[i]<<"\n";
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 16 ms 7004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1965 ms 199340 KB Output is correct
2 Correct 1995 ms 198528 KB Output is correct
3 Correct 1975 ms 198052 KB Output is correct
4 Correct 1998 ms 198664 KB Output is correct
5 Correct 1972 ms 198248 KB Output is correct
6 Correct 2045 ms 199288 KB Output is correct
7 Correct 2021 ms 197396 KB Output is correct
8 Correct 2039 ms 198052 KB Output is correct
9 Correct 26 ms 4700 KB Output is correct
10 Correct 1699 ms 197168 KB Output is correct
11 Correct 1795 ms 197408 KB Output is correct
12 Correct 1762 ms 39376 KB Output is correct
13 Correct 2024 ms 433656 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1292 ms 196808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1965 ms 199340 KB Output is correct
2 Correct 1995 ms 198528 KB Output is correct
3 Correct 1975 ms 198052 KB Output is correct
4 Correct 1998 ms 198664 KB Output is correct
5 Correct 1972 ms 198248 KB Output is correct
6 Correct 2045 ms 199288 KB Output is correct
7 Correct 2021 ms 197396 KB Output is correct
8 Correct 2039 ms 198052 KB Output is correct
9 Correct 26 ms 4700 KB Output is correct
10 Correct 1699 ms 197168 KB Output is correct
11 Correct 1795 ms 197408 KB Output is correct
12 Correct 1762 ms 39376 KB Output is correct
13 Correct 2024 ms 433656 KB Output is correct
14 Incorrect 1292 ms 196808 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 16 ms 7004 KB Output isn't correct
4 Halted 0 ms 0 KB -