Submission #90748

#	Time	Username	Problem	Language	Result	Execution time	Memory
90748		YottaByte	특수한 그래프 (IZhO13_specialg)	C++14	0 / 100	1058 ms	8540 KiB

specialg

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define ll long long

const int N = 1e5, inf = 1e9;

int d[N + 1];
vector < int > v[N + 1];

void dij(int x)
{
	int curd = 1;
	priority_queue < pair < int, int > > pq;
	pq.push( {-curd, x} );
	d[x] = 1;
	while(!pq.empty())
	{
		curd = -pq.top().fr;
		x = pq.top().sc;
		pq.pop();
		
		//cout << x << " " << curd << endl;
		if(curd > d[x]) continue;
		for(int i = 0; i < v[x].size(); i++)
		{
			if(curd + 1 < d[v[x][i]] || d[v[x][i]] == 0)
			{
				d[v[x][i]] = curd + 1;
				pq.push( { -d[v[x][i]], v[x][i] } );
			}
		}
	}
}

main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int x; cin >> x;
		v[i].pb(x);
	}
	
	int m; cin >> m;
	while(m--)
	{
		int t, x, y;
		cin >> t >> x;
		if(t == 1)
		{
			v[x].pop_back();
		}
		else
		{
			cin >> y;
			memset(d, 0, sizeof(d));
			dij(x);
			cout << d[y] - 1 << endl;
		}
	}
}
/*
6
3 3 4 5 6 4
6
2 1 6
2 1 4
2 1 2
1 3
2 1 6
2 1 4
*/

Compilation message (stderr)

specialg.cpp: In function 'void dij(int)':
specialg.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v[x].size(); i++)
                  ~~^~~~~~~~~~~~~
specialg.cpp: At global scope:
specialg.cpp:44:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• Subtask 1: 0 / 100