제출 #934053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934053		vjudge1	Bridges (APIO19_bridges)	C++14	29 / 100	1348 ms	31112 KiB

bridges

#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ptr(x) shared_ptr<x>
#define deb(x) cout << #x << ": " << x << '\n';
struct tpos
{
	int u, w, x;
};
struct edge
{
	int u, v, w;
};
vector<tpos> adj[1<<19];
edge edges[1<<19];
const int inf = 1e9 + 54;
int pos[1<<19];
int visi[1<<19]; int iter = 1;
void dfs(int nodo, int &coche, int &ret)
{
	visi[nodo] = iter; ret++;
	for (tpos t: adj[nodo])
	{
		if (visi[t.u] == iter) continue;
		if (t.w < coche) continue;
		dfs(t.u, coche, ret);
	}
}
void subtask1(int n, int m)
{
	int a, b, w;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> w;
		adj[a].push_back({b, w, i});
		adj[b].push_back({a, w, i});
		edges[i] = {a, b, w};
	}
	int q; cin >> q;
	int tipo;
	while (q--)
	{
		cin >> tipo;
		iter++;
		if (tipo & 1)
		{
			cin >> a >> b;
			edges[a].w = b;
			int u = edges[a].u; int v = edges[a].v;

			for (tpos &e: adj[u])
				if (e.x == a)
				{
					e.w = b;
					break;
				}
			for (tpos &e: adj[v])
				if (e.x == a)
				{
					e.w = b;
					break;
				}
			continue;
		}
		cin >> a >> b;
		int ret = 0;
		dfs(a, b, ret);
		cout << ret << '\n';
	}
}
int n, m;
struct nodo 
{
	int l, r;
	ptr(nodo) lson, rson;
	int val;
};
struct segtree
{
	ptr(nodo) raiz;
	segtree()
	{
		raiz = ptr(nodo) (new nodo);
		build(raiz, 1, n);
	}
	void build(ptr(nodo) node, int l, int r)
	{
		node->l = l; node->r = r;
		if (l == r)
		{
			node->val = pos[l];
			return;
		}
		int mit = l + (r-l)/2;
		node->lson = (ptr(nodo))(new nodo);
		node->rson = (ptr(nodo))(new nodo);
		build(node->lson, l, mit);
		build(node->rson, mit+1, r);
		node->val = min(node->lson->val, node->rson->val);
	}
	void upd (ptr(nodo) node, int pos, int val)
	{
		int l = node->l, r = node->r;
		if (l == pos && r == pos) 
		{
			::pos[pos] = val;
			node->val = val; return;
		}
		if (r < pos || pos < l) return;
		upd(node->lson, pos, val);
		upd(node->rson, pos, val);
		node->val = min(node->lson->val, node->rson->val);
	}
	int query (ptr(nodo) node, int l, int r)
	{
		int L = node->l, R = node->r;
		if (l <= L && R <= r) return node->val;
		if (R < l || r < L ) return inf;
		return min(query(node->lson, l, r), query(node->rson, l, r));
	}
};
int main() 
{
	cin >> n >> m;
	
	if (n <= 1000 && m <= 1000)
	{
		subtask1(n, m);
		return 0;
	} 
	
	int a, b, w;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> w;
		pos[i] = w;
	}
	segtree st;
	int q; cin >> q;
	int tipo;
	int r;
	int pos, peso, coche;
	while (q--)
	{
		cin >> tipo;
		if (tipo & 1)
		{
			cin >> b >> r;
			st.upd(st.raiz, b, r);
			continue;
		}
		cin >> pos >> coche;
		int yo = 0;
		int l = pos, r = n-1;
		int ret = pos;
		while (l <= r)
		{
			//deb(l); deb(r); 
			int mit = (l+r)>>1;// deb(mit);
			int temp = st.query(st.raiz, l, mit);
			
			if (temp >= coche)
			{
				ret = mit;
				l = mit+1;
				continue;
			}
			r = mit-1;
		}
		//cout << ret << '\n'; 
		
		if (::pos[ret] >= coche) ret++;
	//	deb(ret);
		yo += ret - pos;
		l = 1, r = pos-1; ret = -1;

		while (l <= r)
		{
			//deb(l); deb(r); 
			int mit = (l+r)>>1; //deb(mit);
			int temp = st.query(st.raiz, mit, r);
			//deb(temp);
			//cout << "_--------------------\n";
			if (temp >= coche)
			{
				ret = mit;
				r = mit-1;
				continue;
			}
			l = mit+1;
		}
	//	deb(ret);
		yo++;
		 
		//if ( (ret != -1) && ::pos[ret] >= coche) ret--;
		if (ret != -1)
			yo += pos - ret;

		cout << yo << '\n';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:142:11: warning: unused variable 'peso' [-Wunused-variable]
  142 |  int pos, peso, coche;
      |           ^~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27