| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 426408 | 2021-06-14T01:07:30 Z | duality | From Hacks to Snitches (BOI21_watchmen) | C++11 | 143 ms | 33272 KB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
vi adjList[250000];
pair<int,pii> p[250000];
bool comp(int a,int b) {
return p[a] < p[b];
}
int pos[250000];
vector<LLI> dist[250000];
priority_queue<pair<LLI,int> > H;
int relax(int u,LLI d) {
if ((dist[u][d % p[u].first] == -1) || (d < dist[u][d % p[u].first])) {
dist[u][d % p[u].first] = d;
H.push(mp(-d,u));
}
return 0;
}
int done[250000],done2[250000];
set<pii> done3[250000];
int main() {
int i,j;
int N,M,K;
int u,v,l;
scanf("%d %d",&N,&M);
for (i = 0; i < M; i++) {
scanf("%d %d",&u,&v);
u--,v--;
adjList[u].pb(v);
adjList[v].pb(u);
}
scanf("%d",&K);
for (i = 0; i < K; i++) {
scanf("%d",&l);
for (j = 0; j < l; j++) scanf("%d",&v),p[v-1] = mp(l,mp(j,i));
}
for (i = 0; i < N; i++) {
if (p[i].first == 0) p[i].first = 1;
dist[i].resize(p[i].first);
fill(dist[i].begin(),dist[i].end(),-1);
}
for (i = 0; i < N; i++) {
sort(adjList[i].begin(),adjList[i].end(),comp);
while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first == 1)) pos[i]++;
}
dist[0][0] = 0,H.push(mp(0,0));
while (!H.empty()) {
int u = H.top().second;
LLI d = -H.top().first;
H.pop();
if (d > dist[u][d % p[u].first]) continue;
else if (u == N-1) {
printf("%lld\n",d);
return 0;
}
if ((p[u].first == 1) || (((d+1) % p[u].first) != p[u].second.first)) relax(u,d+1);
if (done[u] && (((d+p[u].first-1) % p[u].first) != p[u].second.first)) continue;
for (i = done[u] ? pos[u]:0; i < adjList[u].size(); i++) {
int v = adjList[u][i];
if (p[v].first == 1) relax(v,d+1);
else if (p[u].first == 1) {
if (done2[v]) continue;
else {
for (j = 0; j < p[v].first; j++) {
LLI d2 = d+j+1;
if ((d2 % p[v].first) != p[v].second.first) relax(v,d2);
}
done2[v] = 1;
}
}
else if (p[u].second.second == p[v].second.second) {
if (((d+1) % p[v].first) == p[v].second.first) continue;
if (((d % p[v].first) == p[v].second.first) && (((d+1) % p[u].first) == p[u].second.first)) continue;
relax(v,d+1);
}
else {
if (done3[v].count(mp(d % p[v].first,p[u].first))) continue;
for (j = 0; j < p[v].first; j++) {
LLI d2 = d+(LLI) j*p[u].first+1;
if ((d2 % p[v].first) != p[v].second.first) relax(v,d2);
}
done3[v].insert(mp(d % p[v].first,p[u].first));
}
}
done[u] = 1;
}
printf("impossible\n");
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 42 ms | 25668 KB | Output is correct |
| 2 | Incorrect | 143 ms | 33272 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 43 ms | 25676 KB | Output is correct |
| 2 | Incorrect | 112 ms | 33264 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 43 ms | 25676 KB | Output is correct |
| 2 | Incorrect | 112 ms | 33264 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 43 ms | 25676 KB | Output is correct |
| 2 | Incorrect | 112 ms | 33264 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 42 ms | 25668 KB | Output is correct |
| 2 | Incorrect | 143 ms | 33272 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 42 ms | 25668 KB | Output is correct |
| 2 | Incorrect | 143 ms | 33272 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 42 ms | 25668 KB | Output is correct |
| 2 | Incorrect | 143 ms | 33272 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |