제출 #854214

#제출 시각아이디문제언어결과실행 시간메모리
854214mychecksedadFrom Hacks to Snitches (BOI21_watchmen)C++17
0 / 100
56 ms26448 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' const int N = 3e5+100, M = 1e5+10, K = 2; int n, m, k; array<int, 2> T[N]; vector<int> g[N]; priority_queue<int> best[N]; void solve(){ cin >> n >> m; for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } for(int i = 1; i <= n; ++i) T[i] = {-1, 0}; cin >> k; for(int i = 1; i <= k; ++i){ int x; cin >> x; for(int j = 0; j < x; ++j){ int nod; cin >> nod; T[nod] = {j, x}; } } priority_queue<array<int, 2>> q; for(int j = 0; j < K; ++j) best[1].push(j), q.push({-j, 1}); while(!q.empty()){ int v = q.top()[1], D = -q.top()[0]; q.pop(); if(D > best[v].top()) continue; for(int u: g[v]){ bool passed_over_v = 0; for(int j = 1; j <= K; ++j){ int DD = D + j; if(T[v][0] > -1 && (DD-1) % T[v][1] == T[v][0]) passed_over_v = 1; if(passed_over_v) continue; if(T[v][0] > -1 && T[u][0] > -1 && DD % T[v][1] == T[v][0] && (DD-1) % T[u][1] == T[u][0]){ continue; } if(T[u][0] > -1 && DD % T[u][1] == T[u][0]){ continue; } if(best[u].size() < K){ best[u].push(DD); q.push({-DD, u}); }else if(best[u].top() > DD){ best[u].pop(); best[u].push(DD); q.push({-DD, u}); } } } } if(best[n].empty()) cout << "impossible"; else{ while(best[n].size() > 1) best[n].pop(); cout << best[n].top(); } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

watchmen.cpp: In function 'int main()':
watchmen.cpp:73:15: warning: unused variable 'aa' [-Wunused-variable]
   73 |   int tt = 1, aa;
      |               ^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...