oj.uz

답안 #132250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132250 2019-07-18T15:00:04 Z MvC 다리 (APIO19_bridges) C++11
43 / 100
 1198 ms 57984 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
//#include "job.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mmax=1e3+50;
const int mod=1e9+7;
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> order_set;
int rs,x,y,z,nr,vz[mmax],q,i,t,n,m,vl[nmax],st[4*nmax],l,r,mid,lb,rb,p[nmax],sz[nmax],ans[nmax],j,w[nmax],par[nmax];
vector<pair<pair<int,int>,int> >e;
vector<pair<int,pair<int,int> > >ne,qr;
vector<int>a[nmax];
order_set s[nmax];
pair<int,int>pa;
void dfs(int x,int z)
{
	vz[x]=1;
	nr++;
	for(int i=0;i<a[x].size();i++)
	{
		int y=a[x][i],u=x^e[y].fr.fr^e[y].fr.sc;
		if(vz[u] || e[y].sc<z)continue;
		dfs(u,z);
	}
}
void upd(int nod,int l,int r,int p)
{
	if(l==r)
	{
		st[nod]=vl[l];
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid)upd(2*nod,l,mid,p);
	else upd(2*nod+1,mid+1,r,p);
	st[nod]=min(st[2*nod],st[2*nod+1]);
}
int qry(int nod,int l,int r,int tl,int tr)
{
	if(tr<l || tl>r)return inf;
	if(tl<=l && r<=tr)return st[nod];
	int mid=(l+r)/2;
	return min(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int fnd(int x)
{
    if(p[x]==x)return x;
    return p[x]=fnd(p[x]);
}
void uni(int x,int y)
{
    x=fnd(x);
    y=fnd(y);
    if(x!=y)
    {
        if(sz[x]<sz[y])swap(x,y);
        p[y]=x;
        sz[x]+=sz[y];
    }
}
void dfs1(int x,int pr,int z)
{
	w[x]=z;
	par[x]=pr;
	for(int i=0;i<a[x].size();i++)
	{
		int y=a[x][i],u=x^e[y].fr.fr^e[y].fr.sc;
		if(u==pr)continue;
		dfs1(u,x,e[y].sc);
	}
}
void ad(int x)
{
	int y=x,mn=inf;
	while(x)
	{
		s[x].in(mkp(mn,y));
		//cout<<x<<" "<<mn<<" "<<y<<endl;
		mn=min(mn,w[x]);
		x=par[x];
	}
}
void re(int x)
{
	int y=x,mn=inf;
	while(x)
	{
		if(s[x].fd(mkp(mn,y))!=s[x].end())s[x].er(s[x].fd(mkp(mn,y)));
		mn=min(mn,w[x]);
		x=par[x];
	}
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=4*n;i++)st[i]=inf;
	for(i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		a[x].pb(i-1);
		a[y].pb(i-1);
		e.pb(mkp(mkp(x,y),z));
		vl[x]=z;
		upd(1,1,n,x);
	}
	for(i=1;i<=15;i++)if((1<<i)==n+1)break;
	cin>>q;
	if((1<<i)==n+1 && m==n-1)
	{
	    dfs1(1,0,0);
	    for(i=1;i<=n;i++)
	    {
	    	ad(i);
		}
		/*for(i=1;i<=n;i++)
		{
			cout<<i<<endl;
			for(auto it=s[i].begin();it!=s[i].end();it++)
			{
				pa=(*it);
				cout<<pa.fr<" "<<pa.sc<endl;
			}
			cout<<endl<<endl;
		}*/
		while(q--)
		{
			cin>>t>>x>>z;
			if(t==1)
			{
				x--;
				e[x].sc=z;
				if(e[x].fr.fr==par[e[x].fr.sc])y=e[x].fr.sc;
				else y=e[x].fr.fr;
				re(y);
				w[y]=z;
				ad(y);
			}
			else
			{
				while(x)
				{
					if(w[x]<z)break;
					x=par[x];
				}
				z--;
				if(s[x].upper_bound(mkp(z,1e6))==s[x].end())rs=1;
				else
				{
					pa=*s[x].upper_bound(mkp(z,1e6));
					rs=(int)s[x].size()-s[x].order_of_key(pa);
				}
				cout<<rs<<'\n';
			}
		}
	}
	else if(n<=1000 && m<=1000 && q<=10000)
	{
		while(q--)
		{
			cin>>t>>x>>z;
			if(t==1)
			{
				x--;
				e[x].sc=z;
			}
			else
			{
				memset(vz,0,sizeof(vz));
				nr=0;
				dfs(x,z);
				cout<<nr<<'\n';
			}
		}
		return 0;
	}
	else if(m==n-1)
	{
		while(q--)
		{
			cin>>t>>x>>z;
			if(t==1)
			{
				x--;
				e[x].sc=z;
				vl[e[x].fr.fr]=z;
				upd(1,1,n,e[x].fr.fr);
			}
			else
			{
				l=1,r=x-1,lb=-1;
				while(l<=r)
				{
					mid=(l+r)/2;
					if(qry(1,1,n,mid,x-1)>=z)lb=mid,r=mid-1;
					else l=mid+1;
				}
				l=x,r=n-1,rb=-1;
				while(l<=r)
				{
					mid=(l+r)/2;
					if(qry(1,1,n,x,mid)>=z)rb=mid,l=mid+1;
					else r=mid-1;
				}
				if(lb==-1 && rb==-1)cout<<1<<'\n';
				else if(lb==-1)cout<<rb+1-x+1<<'\n';
				else if(rb==-1)cout<<x-lb+1<<'\n';
				else cout<<rb+1-lb+1<<'\n';
			}
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			p[i]=i;
			sz[i]=1;
		}
		for(i=0;i<m;i++)
		{
			ne.pb(mkp(e[i].sc,mkp(e[i].fr.fr,e[i].fr.sc)));
		}
		sort(ne.begin(),ne.end());
		reverse(ne.begin(),ne.end());
		for(i=1;i<=q;i++)
		{
			cin>>t>>x>>z;
			qr.pb(mkp(z,mkp(x,i)));
		}
		sort(qr.begin(),qr.end());
		reverse(qr.begin(),qr.end());
		for(i=0;i<q;i++)
		{
			for(;j<m;j++)
			{
				if(ne[j].fr<qr[i].fr)break;
				uni(ne[j].sc.fr,ne[j].sc.sc);
			}
			ans[qr[i].sc.sc]=sz[fnd(qr[i].sc.fr)];
		}
		for(i=1;i<=q;i++)cout<<ans[i]<<'\n';
	}
    return 0;
}
/*
7 6
1 2 3
1 3 4
2 4 4
2 5 5
3 6 2
3 7 10
*/

Compilation message

bridges.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
bridges.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
bridges.cpp: In function 'void dfs1(int, int, int)':
bridges.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12152 KB Output is correct
2 Correct 16 ms 12152 KB Output is correct
3 Correct 70 ms 12152 KB Output is correct
4 Correct 20 ms 12156 KB Output is correct
5 Correct 24 ms 12152 KB Output is correct
6 Correct 23 ms 12152 KB Output is correct
7 Correct 23 ms 12152 KB Output is correct
8 Correct 24 ms 12152 KB Output is correct
9 Correct 25 ms 12152 KB Output is correct
10 Correct 22 ms 12152 KB Output is correct
11 Correct 21 ms 12152 KB Output is correct
12 Correct 22 ms 12152 KB Output is correct
13 Correct 25 ms 12152 KB Output is correct
14 Correct 24 ms 12156 KB Output is correct
15 Correct 25 ms 12152 KB Output is correct
16 Correct 23 ms 12152 KB Output is correct
17 Correct 23 ms 12152 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 15280 KB Output is correct
2 Correct 438 ms 15304 KB Output is correct
3 Correct 438 ms 15408 KB Output is correct
4 Correct 437 ms 15540 KB Output is correct
5 Correct 442 ms 15536 KB Output is correct
6 Correct 473 ms 15536 KB Output is correct
7 Correct 480 ms 15536 KB Output is correct
8 Correct 485 ms 15660 KB Output is correct
9 Correct 57 ms 12280 KB Output is correct
10 Correct 473 ms 15536 KB Output is correct
11 Correct 446 ms 15532 KB Output is correct
12 Correct 764 ms 15840 KB Output is correct
13 Correct 178 ms 15280 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1198 ms 57984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 20188 KB Output is correct
2 Correct 57 ms 12344 KB Output is correct
3 Correct 82 ms 16552 KB Output is correct
4 Correct 88 ms 16576 KB Output is correct
5 Correct 172 ms 20308 KB Output is correct
6 Correct 175 ms 20264 KB Output is correct
7 Correct 166 ms 20268 KB Output is correct
8 Correct 124 ms 18080 KB Output is correct
9 Correct 123 ms 18200 KB Output is correct
10 Correct 124 ms 18336 KB Output is correct
11 Correct 154 ms 19124 KB Output is correct
12 Correct 163 ms 19084 KB Output is correct
13 Correct 152 ms 19108 KB Output is correct
14 Correct 169 ms 20184 KB Output is correct
15 Correct 170 ms 20336 KB Output is correct
16 Correct 188 ms 19680 KB Output is correct
17 Correct 176 ms 19716 KB Output is correct
18 Correct 172 ms 19756 KB Output is correct
19 Correct 177 ms 19812 KB Output is correct
20 Correct 158 ms 19340 KB Output is correct
21 Correct 160 ms 19368 KB Output is correct
22 Correct 189 ms 19624 KB Output is correct
23 Correct 144 ms 19072 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 15280 KB Output is correct
2 Correct 438 ms 15304 KB Output is correct
3 Correct 438 ms 15408 KB Output is correct
4 Correct 437 ms 15540 KB Output is correct
5 Correct 442 ms 15536 KB Output is correct
6 Correct 473 ms 15536 KB Output is correct
7 Correct 480 ms 15536 KB Output is correct
8 Correct 485 ms 15660 KB Output is correct
9 Correct 57 ms 12280 KB Output is correct
10 Correct 473 ms 15536 KB Output is correct
11 Correct 446 ms 15532 KB Output is correct
12 Correct 764 ms 15840 KB Output is correct
13 Correct 178 ms 15280 KB Output is correct
14 Incorrect 1198 ms 57984 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12152 KB Output is correct
2 Correct 16 ms 12152 KB Output is correct
3 Correct 70 ms 12152 KB Output is correct
4 Correct 20 ms 12156 KB Output is correct
5 Correct 24 ms 12152 KB Output is correct
6 Correct 23 ms 12152 KB Output is correct
7 Correct 23 ms 12152 KB Output is correct
8 Correct 24 ms 12152 KB Output is correct
9 Correct 25 ms 12152 KB Output is correct
10 Correct 22 ms 12152 KB Output is correct
11 Correct 21 ms 12152 KB Output is correct
12 Correct 22 ms 12152 KB Output is correct
13 Correct 25 ms 12152 KB Output is correct
14 Correct 24 ms 12156 KB Output is correct
15 Correct 25 ms 12152 KB Output is correct
16 Correct 23 ms 12152 KB Output is correct
17 Correct 23 ms 12152 KB Output is correct
18 Correct 435 ms 15280 KB Output is correct
19 Correct 438 ms 15304 KB Output is correct
20 Correct 438 ms 15408 KB Output is correct
21 Correct 437 ms 15540 KB Output is correct
22 Correct 442 ms 15536 KB Output is correct
23 Correct 473 ms 15536 KB Output is correct
24 Correct 480 ms 15536 KB Output is correct
25 Correct 485 ms 15660 KB Output is correct
26 Correct 57 ms 12280 KB Output is correct
27 Correct 473 ms 15536 KB Output is correct
28 Correct 446 ms 15532 KB Output is correct
29 Correct 764 ms 15840 KB Output is correct
30 Correct 178 ms 15280 KB Output is correct
31 Incorrect 1198 ms 57984 KB Output isn't correct
32 Halted 0 ms 0 KB -