Submission #760540

#	Time	Username	Problem	Language	Result	Execution time	Memory
760540		Marceantasy	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	79 ms	15684 KiB

watchmen

#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 = 1e5+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 &n)const{
        return dist > n.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){
                    newlist.push_back(y);
                    continue;
                }
                auto promotionate = [&](ll x, ll cyc, ll xz){
                    ll ff = (x/cyc) * cyc + m;
                    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 >= 1e16) 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){
      |                                                                                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:83:40: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   83 |                     if(val%d[v].size() != cycles[v].second){
      |                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:90:43: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   90 |                         if(ff%d[v].size() != cycles[v].second) enq(y, ff+1);
      |                            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:94:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                     if(cycles[y].second == (cycles[v].second+1)%d[v].size() || cycles[v].second == (cycles[y].second +1)%d[v].size()){
watchmen.cpp:94:97: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                     if(cycles[y].second == (cycles[v].second+1)%d[v].size() || cycles[v].second == (cycles[y].second +1)%d[v].size()){

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20