Submission #1201556

#TimeUsernameProblemLanguageResultExecution timeMemory
1201556shn벽 칠하기 (APIO20_paint)C++17
100 / 100
118 ms18760 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A,vector<vector<int>> B){ vector < int > g[K + 3] , d[N + 3]; for(int i = 0; i < M; i++){ for(int j = 0; j < A[i]; j++){ // cout << i << ' ' << B[i][j] << '\n'; g[B[i][j]].push_back(i); } } vector < pair < int , int > > v; int last[2][M]; for(int i = 0; i < 2; i++){ for(int j = 0; j < M; j++) last[i][j] = -2; } for(int i = 0; i < N; i++){ if(i > 1){ for(int it : g[C[i - 2]]){ last[i & 1][it] = -2; } } bool ok = 0; for(int it : g[C[i]]){ int prev = it - 1; if(prev == -1) prev = M - 1; if(last[(i & 1) ^ 1][prev] == -2) last[i & 1][it] = i - 1; else last[i & 1][it] = last[(i & 1) ^ 1][prev]; if(last[i & 1][it] + M <= i && !ok){ d[i - M + 1].push_back(i + 1); ok = 1; // cout << i - M + 1 << ' ' << i << '\n'; } // cout << i << ' ' << it << ' ' << prev << ' ' << last[i & 1][it] << ' ' << last[i & 1][it] + M - 1 << '\n'; } } int dst[N + 1]; for(int i = 1; i <= N; i++){ dst[i] = 1e9; d[i].push_back(i - 1); } dst[0] = 0; queue < int > q; q.push(0); while(q.size() > 0){ int v = q.front(); q.pop(); for(int to : d[v]){ if(to == v - 1){ if(dst[to] > dst[v]){ dst[to] = dst[v]; q.push(to); } } else{ if(dst[to] > dst[v] + 1){ dst[to] = dst[v] + 1; q.push(to); } } } } if(dst[N] == 1e9) return -1; return dst[N]; } // int main(){ // int N , M , K; // cin >> N >> M >> K; // vector < int > C(N); // for(int i = 0; i < N; i++){ // cin >> C[i]; // } // vector < int > A(M); // vector < vector < int > > B(M); // for(int i = 0; i < M; i++){ // cin >> A[i]; // for(int j = 0; j < A[i]; j++){ // int x; // cin >> x; // B[i].push_back(x); // } // } // cout << minimumInstructions(N , M , K , C , A , B); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...