oj.uz

답안 #90748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90748 2018-12-24T08:39:04 Z YottaByte 특수한 그래프 (IZhO13_specialg) C++14
0 / 100
 1000 ms 8540 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 3320 KB Output is correct
2 Correct 65 ms 3320 KB Output is correct
3 Correct 74 ms 3348 KB Output is correct
4 Correct 193 ms 3520 KB Output is correct
5 Correct 83 ms 3580 KB Output is correct
6 Correct 602 ms 3992 KB Output is correct
7 Correct 734 ms 4352 KB Output is correct
8 Correct 639 ms 4472 KB Output is correct
9 Correct 660 ms 4736 KB Output is correct
10 Correct 651 ms 4972 KB Output is correct
11 Execution timed out 1058 ms 8540 KB Time limit exceeded
12 Halted 0 ms 0 KB -