Submission #408770

#	Time	Username	Problem	Language	Result	Execution time	Memory
408770		ly20	From Hacks to Snitches (BOI21_watchmen)	C++17	15 / 100	6098 ms	211736 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 251234;
const long long INF = 1123456789012345678;
vector <int> gf[MAXN], grafo[MAXN];
int id;
map <pair <int, int>, int> mp;
long long dist[MAXN];
vector <int> cic[MAXN];
int inv[MAXN];
vector <pair <int, int> > nodes;
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int k;
    for(int i = 1; i <= n; i++) {
        inv[i] = -1;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        gf[a].push_back(b); gf[b].push_back(a);
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        int t;
        scanf("%d", &t);
        for(int j = 0; j < t; j++) {
            int a;
            scanf("%d", &a);
            inv[a] = i;
            cic[i].push_back(a);
            //printf("oi\n");
        }
    }
    for(int i = 1; i <= n; i++) {
        if(inv[i] == -1) {
            mp[make_pair(i, 0)] = id++;
            nodes.push_back(make_pair(i, 0));
        }
        else {
            int c = inv[i];
            for(int j = 0; j < cic[c].size(); j++) {
                mp[make_pair(i, j)] = id++;
                nodes.push_back(make_pair(i, j));
            }
        }
    }
    //printf("%d\n", nodes.size());
    for(int i = 0; i < nodes.size(); i++) {
        dist[i] = INF;
        pair <int, int> cur = nodes[i];
        //printf("%d %d %d %d\n", i, cur.first, cur.second, inv[cur.first]);
        if(inv[cur.first] == -1) {
            for(int j = 0; j < gf[cur.first].size(); j++) {
                int viz = gf[cur.first][j];
                if(inv[viz] != -1) continue;
                int vzn = mp[make_pair(viz, 0)];
                grafo[i].push_back(vzn);
            }
        }
        else {
                //printf("oi\n");
            if(cic[inv[cur.first]][cur.second] == cur.first) continue;
        //printf("oi2\n");
            for(int j = 0; j < gf[cur.first].size(); j++) {
                int viz = gf[cur.first][j];
            //printf("%d\n", viz);
                if(inv[viz] == -1) {
                    int vzn = mp[make_pair(viz, 0)];
                    grafo[i].push_back(vzn);
                    grafo[vzn].push_back(i);
                }
                else {
                    int pr = (cur.second + 1) % (cic[inv[cur.first]].size());
                    //printf("oi\n");
                    if(cic[inv[viz]][pr] == viz || (cic[inv[viz]][pr] == cur.first && cic[inv[viz]][cur.second] == viz)) continue;
                    //printf("%d %d\n", viz, pr);
                    int vzn = mp[make_pair(viz, pr)];
                    grafo[i].push_back(vzn);
                    //grafo[vzn].push_back(i);
                }
            }
        }
    }
    dist[0] = 0;
    set <pair <long long, int> > s;
    for(int i = 0; i < nodes.size(); i++) {
        s.insert(make_pair(dist[i], i));
    }
    while(!s.empty()) {
        int cur = (*s.begin()).second;
        s.erase(s.begin());
        //int cz = nodes[cur].first;
        for(int i = 0; i < grafo[cur].size(); i++) {
            int viz = grafo[cur][i];
            int vz = nodes[viz].first, md = nodes[viz].second;
            long long d1 = dist[cur] + 1;
            int tam;
            if(inv[vz] != -1) {
                tam = cic[inv[vz]].size();
                if(md != d1 % tam) {
                    if(d1 % tam <= md)d1 = d1 + (md - d1 % tam);
                    else d1 = d1 + (md - d1 % tam + tam);
                }
            }
            if(d1 < dist[viz]) {
                s.erase(make_pair(dist[viz], viz));
                dist[viz] = d1;
                s.insert(make_pair(dist[viz], viz));
            }
        }
    }
    /*for(int i = 0; i < nodes.size(); i++) {
        printf("%d %d %lld\n", nodes[i].first, nodes[i].second, dist[i]);
    }*/
    if(dist[id - 1] < INF) printf("%lld\n", dist[id - 1]);
    else printf("impossible\n");
    return 0;
}

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int j = 0; j < cic[c].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~
watchmen.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < nodes.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
watchmen.cpp:55:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int j = 0; j < gf[cur.first].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~
watchmen.cpp:66:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int j = 0; j < gf[cur.first].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~
watchmen.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0; i < nodes.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
watchmen.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int i = 0; i < grafo[cur].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
watchmen.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~
watchmen.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |             scanf("%d", &a);
      |             ~~~~~^~~~~~~~~~

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