Submission #760547

#TimeUsernameProblemLanguageResultExecution timeMemory
760547MarceantasyFrom Hacks to Snitches (BOI21_watchmen)C++17
0 / 100
77 ms23924 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ar array #define rep(i, n) for(int i = 0; i<(int)n; ++i) const int mxN = 3e5+5, M = 1e9+7; vector<ll> d[mxN]; vector<int> adj[mxN]; int n, m; struct node{ int x, y; ll dist; bool operator<(const node &other)const{ return dist > other.dist; } }; void solve(int n, vector<pair<int, int>> edg, vector<int> v, int s, int t){ for(auto &[a, b] : edg){ adj[a].push_back(b); adj[b].push_back(a); } rep(i, n) sort(adj[i].begin(), adj[i].end()); int p = 0; vector<pair<int, int>> cycles; for(int i = 0; i<v.size(); ++i){ for(int j = 0; j<v[i]; ++j){ d[p++].resize(v[i], 1e18); cycles.emplace_back(i, j); } } while(p<n){ d[p++].resize(1, 1e18); cycles.emplace_back(-1, 0); } priority_queue<node> pq; auto enq = [&](int v, ll dist){ if(d[v].size() > 1 && dist%d[v].size() == cycles[v].second) return; if(d[v][dist%d[v].size()] > dist){ d[v][dist%d[v].size()] = dist; pq.push({v, (int)(dist%d[v].size()), dist}); } }; enq(s, 0); vector<int> viscnt(n); while(pq.size()){ auto x = pq.top(); pq.pop(); int v = x.x; int w = x.y; if(d[v][w] != x.dist) continue; enq(v, x.dist+1); viscnt[v]++; if(d[v].size() == 1){ for(auto &y : adj[v]){ if(cycles[v].first >= 0 && cycles[v].first == cycles[y].first && w == cycles[y].second && (w+1)%d[v].size() == cycles[v].second){ continue; } enq(y, x.dist+1); enq(y, x.dist+1 + ((cycles[y].second-x.dist)%d[y].size()+d[y].size()) % d[y].size()); } }else{ vector<int> newlist; for(auto &y : adj[v]){ if(cycles[v].first >= 0 && cycles[v].first == cycles[y].first && (w+1)%d[v].size() == cycles[v].second && w == cycles[y].second){ newlist.push_back(y); continue; } auto promotionate = [&](ll x, ll cyc, ll xz){ ll ff = (x/cyc) * cyc + xz; if(ff < x) ff += cyc; return ff; }; if(d[y].size() == 1){ enq(y, x.dist+1); }else if(cycles[v].first != cycles[y].first){ enq(y, x.dist+1); ll val = promotionate(x.dist+1, d[y].size(), cycles[y].second); if(val%d[v].size() != cycles[v].second){ enq(y, val+1); }else{ newlist.push_back(y); ll newdist = promotionate(val, d[v].size(), w); enq(y, newdist+1); ll ff = promotionate(newdist+1, d[y].size(), cycles[y].second); if(ff%d[v].size() != cycles[v].second) enq(y, ff+1); } }else{ enq(y, x.dist+1); if(cycles[y].second == (cycles[v].second+1)%d[v].size() || cycles[v].second == (cycles[y].second +1)%d[v].size()){ newlist.push_back(y); }else{ ll ff = promotionate(x.dist+1, d[y].size(), cycles[y].second); enq(y, ff+1); } } } adj[v] = newlist; } } ll ans = *min_element(d[t].begin(), d[t].end()); if(ans >= 1e18) cout << "impossible\n"; else cout << ans << "\n"; } int main(){ #ifdef _DEBUG // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); cin >> n >> m; vector<pair<int, int>> edg; rep(i, m){ int a, b; cin >> a >> b, --a, --b; edg.emplace_back(a, b); } vector<int> idx(n, -1); int cnt = 0; int k; cin >> k; vector<int> ff(k); rep(i, k){ cin >> ff[i]; rep(j, ff[i]){ int x; cin >> x, --x; idx[x] = cnt++; } } rep(i, n){ if(idx[i] == -1) idx[i] = cnt++; } for(int i = 0; i<m; ++i){ edg[i] = {idx[edg[i].first], idx[edg[i].second]}; } solve(n, edg, ff, idx[0], idx[n-1]); }

Compilation message (stderr)

watchmen.cpp: In function 'void solve(int, std::vector<std::pair<int, int> >, std::vector<int>, int, int)':
watchmen.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0; i<v.size(); ++i){
      |                    ~^~~~~~~~~
watchmen.cpp: In lambda function:
watchmen.cpp:41:48: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   41 |         if(d[v].size() > 1 && dist%d[v].size() == cycles[v].second) return;
      |                               ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp: In function 'void solve(int, std::vector<std::pair<int, int> >, std::vector<int>, int, int)':
watchmen.cpp:59:125: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |                 if(cycles[v].first >= 0 && cycles[v].first == cycles[y].first && w == cycles[y].second && (w+1)%d[v].size() == cycles[v].second){
      |                                                                                                           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:68:100: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |                 if(cycles[v].first >= 0 && cycles[v].first == cycles[y].first && (w+1)%d[v].size() == cycles[v].second && w == cycles[y].second){
      |                                                                                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:82:40: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   82 |                     if(val%d[v].size() != cycles[v].second){
      |                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:89:43: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   89 |                         if(ff%d[v].size() != cycles[v].second) enq(y, ff+1);
      |                            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:93:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                     if(cycles[y].second == (cycles[v].second+1)%d[v].size() || cycles[v].second == (cycles[y].second +1)%d[v].size()){
watchmen.cpp:93:97: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                     if(cycles[y].second == (cycles[v].second+1)%d[v].size() || cycles[v].second == (cycles[y].second +1)%d[v].size()){
#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...