oj.uz

Submission #408870

# Submission time Handle Problem Language Result Execution time Memory
408870 2021-05-19T18:25:41 Z peuch From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 318 ms 34236 KB 
#include<bits/stdc++.h>
using namespace std;
 
const int MAXN = 250010;
const long long INF = 1e15;
 
/*
 
Expansão de vértice em 2:
 - 2 * i -> menor tempo possível;
 - 2 * i + 1 -> menor tempo possível depois que o guarda passa;
 
*/
 
int n, m, c;
long long dist[2 * MAXN];
int marc[MAXN];
int cycleLen[2 * MAXN], cycleID[2 * MAXN], cycle[2 * MAXN];
 
vector<int> ar[2 * MAXN];
 
void dijkstra();
 
int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		
		a <<= 1;
		b <<= 1;
		
		ar[a].push_back(b);
		ar[a].push_back(b + 1);
		ar[a + 1].push_back(b);
		ar[a + 1].push_back(b + 1);
		
		ar[b].push_back(a);
		ar[b].push_back(a + 1);
		ar[b + 1].push_back(a);
		ar[b + 1].push_back(a + 1);
	
	}
	scanf("%d", &c);
	for(int i = 1; i <= c; i++){
		int l;
		scanf("%d", &l);
		for(int j = 0; j < l; j++){
			int a, b;
			scanf("%d", &a);
			a <<= 1;
			b = a | 1;
			cycleLen[a] = cycleLen[b] = l;
			cycleID[a] = cycleID[b] = j;
			cycle[a] = cycle[b] = i;
		}
	}
	dijkstra();
	long long ans = min(dist[2 * n], dist[2 * n + 1]);
	if(ans >= INF) printf("impossible\n");
	else printf("%lld\n", ans);
}
 
void dijkstra(){
	set<pair<long long, int> > s;
	for(int i = 2; i <= 2 * n + 1; i++){
		dist[i] = INF;
		if((i >> 1) == 1) dist[i] = 0;
		s.insert(make_pair(dist[i], i));
	}
	while(!s.empty()){
		int cur = s.begin()->second;
//		printf("dist[%d][%d] = %lld\n", cur >> 1, cur & 1, dist[cur]);
		marc[cur] = 1;
		s.erase(s.begin());
		for(int i = 0; i < ar[cur].size(); i++){
			int viz = ar[cur][i];
			if(marc[viz]) continue;
			if((viz & 1) && cycleLen[viz] != 0){
				long long tempoEsperando = (cycleID[viz] + cycleLen[viz] - (dist[cur] % cycleLen[viz])) % cycleLen[viz];
				if(cycleLen[cur] != 0 && tempoEsperando >= (cycleID[cur] + cycleLen[cur] - (dist[cur] % cycleLen[cur])) % cycleLen[cur]) continue;
				if(cycleLen[cur] != 0 && cycle[cur] == cycle[viz] && cycleID[cur] == (cycleID[viz] + 1) % cycleLen[cur]) continue;
				long long auxD = dist[cur] + tempoEsperando + 1;
				if(auxD >= dist[viz]) continue;
				s.erase(make_pair(dist[viz], viz));
				s.insert(make_pair(dist[viz] = auxD, viz));
			}
			else{
				long long auxD = dist[cur] + 1;
				if(cycleLen[cur] != 0 && cycle[cur] == cycle[viz] && cycleID[cur] == (cycleID[viz] + 1) % cycleLen[cur] && auxD % cycleLen[cur] == cycleID[cur]) continue;
				if(cycleLen[viz] != 0 && auxD % cycleLen[viz] == cycleID[viz]){
					if(cycleLen[cur] != 0 && auxD % cycleLen[cur] == cycleID[cur]) continue;
					auxD++;
				}
				if(cycleLen[cur] != 0 && cycle[cur] == cycle[viz] && cycleID[cur] == (cycleID[viz] + 1) % cycleLen[cur] && auxD % cycleLen[cur] == cycleID[cur]) continue;
				if(auxD >= dist[viz]) continue;
				s.erase(make_pair(dist[viz], viz));
				s.insert(make_pair(dist[viz] = auxD, viz));
			}
		}
	}
}

Compilation message

watchmen.cpp: In function 'void dijkstra()':
watchmen.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i = 0; i < ar[cur].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
watchmen.cpp: In function 'int main()':
watchmen.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d", &c);
      |  ~~~~~^~~~~~~~~~
watchmen.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d", &l);
      |   ~~~~~^~~~~~~~~~
watchmen.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |    scanf("%d", &a);
      |    ~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15592 KB Output is correct
2 Incorrect 316 ms 34216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15564 KB Output is correct
2 Incorrect 318 ms 34236 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15564 KB Output is correct
2 Incorrect 318 ms 34236 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15564 KB Output is correct
2 Incorrect 318 ms 34236 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15592 KB Output is correct
2 Incorrect 316 ms 34216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15592 KB Output is correct
2 Incorrect 316 ms 34216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15592 KB Output is correct
2 Incorrect 316 ms 34216 KB Output isn't correct
3 Halted 0 ms 0 KB -