oj.uz

Submission #402241

# Submission time Handle Problem Language Result Execution time Memory
402241 2021-05-11T12:56:58 Z rrrr10000 From Hacks to Snitches (BOI21_watchmen) C++14
25 / 100
 1680 ms 451632 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=998244353;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
inline ll readll() {
    ll x = 0;
    int neg=1;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9'){
        if(ch=='-')neg=-1;
        ch = getchar_unlocked();
    }
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x*neg;
}
int main(){
    ll n=readll(),m=readll();
    // map<P,ll> edges;
    vvp g(n);
    rep(i,m){
        ll a=readll()-1,b=readll()-1;
        g[a].pb(b,i);g[b].pb(a,i);
        // edges[P(min(a,b),max(a,b))]=i;
    }
    ll k=readll();
    vi len(n,1),ngv(n,-1),nge(m,-1);
    vvp sp(n);
    rep(j,k){
        ll l=readll();
        vi v(l);
        rep(i,l)v[i]=readll()-1;
        rep(i,l){
            ngv[v[i]]=i;len[v[i]]=l;
            // ll id=edges[P(min(v[i],v[(i+1)%l]),max(v[i],v[(i+1)%l]))];
            // nge[id]=i;
            if(i==l-1&&l==2)break;
            sp[v[i]].pb(v[(i+1)%l],i);
            sp[v[(i+1)%l]].pb(v[i],i);
        }
    }
    rep(i,n)for(auto x:g[i]){
        for(auto&y:sp[i])if(y.fi==x.fi){
            nge[x.se]=y.se;
            y.se=x.se;
        }
    }
    vb ok(n,false);
    rep(i,n)for(auto x:g[i])if(ngv[x.fi]==-1)ok[i]=true;
    vvi dis(n);
    rep(i,n)dis[i]=vi(len[i],inf);
    dis[0][0]=0;
    vi dis2(n,inf);
    queue<P> que,que2;
    que.emplace(0,0);
    ll s=0;
    rep(i,n)s+=dis[i].size();
    assert(s<=400000);
    ll cnt=0;
    while(!que.empty()||!que2.empty()){
        cnt++;
        assert(cnt<=500000000);
        while(que2.size()&&(que.empty()||que2.front().fi==que.front().fi)){
            que.push(que2.front());que2.pop();
        }
        ll i=que.front().fi,j=que.front().se,cost=dis[i][j];que.pop();
        if(chmin(dis2[i],cost)){
            for(auto x:g[i]){
                cnt++;
                bool f=true;
                for(auto y:sp[i])if(x==y)f=false;
                if(!f)continue;
                ll nc=cost+1,p=nc%len[x.fi];
                if(ngv[x.fi]==p){
                    nc++;p++;if(p>=len[x.fi])p-=len[x.fi];
                }
                if(chmin(dis[x.fi][p],nc))que.emplace(x.fi,p);
            }
        }
        for(auto x:sp[i]){
            ll p0=cost%len[x.fi],p1=p0+1;if(p1>=len[x.fi])p1-=len[x.fi];
            cnt++;
            if(nge[x.se]==p0)continue;
            if(ngv[x.fi]==p1)continue;
            if(chmin(dis[x.fi][p1],cost+1))que.emplace(x.fi,p1);
        }
        ll p1=(cost+1)%len[i],p2=p1+1;if(p2>=len[i])p2-=len[i];
        if(ngv[i]==p1){
            if(ok[i]&&chmin(dis[i][p2],cost+2))que.emplace(i,p2);
        }
        else if(chmin(dis[i][p1],cost+1))que2.emplace(i,p1);
    }
    ll ans=inf;
    for(ll x:dis[n-1])chmin(ans,x);
    if(ans==inf)out("impossible");
    else out(ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4428 KB Output is correct
2 Correct 107 ms 18632 KB Output is correct
3 Correct 94 ms 17512 KB Output is correct
4 Correct 85 ms 17604 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 79 ms 17644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4428 KB Output is correct
2 Correct 108 ms 18700 KB Output is correct
3 Correct 80 ms 17476 KB Output is correct
4 Correct 80 ms 17596 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 76 ms 17640 KB Output is correct
7 Correct 87 ms 17448 KB Output is correct
8 Correct 80 ms 17368 KB Output is correct
9 Correct 100 ms 17208 KB Output is correct
10 Correct 74 ms 17348 KB Output is correct
11 Correct 75 ms 17324 KB Output is correct
12 Correct 75 ms 17472 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4428 KB Output is correct
2 Correct 108 ms 18700 KB Output is correct
3 Correct 80 ms 17476 KB Output is correct
4 Correct 80 ms 17596 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 76 ms 17640 KB Output is correct
7 Correct 87 ms 17448 KB Output is correct
8 Correct 80 ms 17368 KB Output is correct
9 Correct 100 ms 17208 KB Output is correct
10 Correct 74 ms 17348 KB Output is correct
11 Correct 75 ms 17324 KB Output is correct
12 Correct 75 ms 17472 KB Output is correct
13 Correct 9 ms 4428 KB Output is correct
14 Correct 108 ms 18680 KB Output is correct
15 Correct 78 ms 17460 KB Output is correct
16 Correct 85 ms 17608 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 74 ms 17580 KB Output is correct
19 Correct 87 ms 17340 KB Output is correct
20 Correct 76 ms 17400 KB Output is correct
21 Correct 99 ms 17240 KB Output is correct
22 Correct 81 ms 17448 KB Output is correct
23 Correct 79 ms 17328 KB Output is correct
24 Correct 76 ms 17512 KB Output is correct
25 Correct 1649 ms 197344 KB Output is correct
26 Correct 1280 ms 225712 KB Output is correct
27 Correct 1212 ms 202488 KB Output is correct
28 Correct 1152 ms 213444 KB Output is correct
29 Correct 1284 ms 177240 KB Output is correct
30 Correct 1253 ms 186208 KB Output is correct
31 Correct 1452 ms 235768 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4428 KB Output is correct
2 Correct 108 ms 18700 KB Output is correct
3 Correct 80 ms 17476 KB Output is correct
4 Correct 80 ms 17596 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 76 ms 17640 KB Output is correct
7 Correct 87 ms 17448 KB Output is correct
8 Correct 80 ms 17368 KB Output is correct
9 Correct 100 ms 17208 KB Output is correct
10 Correct 74 ms 17348 KB Output is correct
11 Correct 75 ms 17324 KB Output is correct
12 Correct 75 ms 17472 KB Output is correct
13 Correct 9 ms 4428 KB Output is correct
14 Correct 108 ms 18680 KB Output is correct
15 Correct 78 ms 17460 KB Output is correct
16 Correct 85 ms 17608 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 74 ms 17580 KB Output is correct
19 Correct 87 ms 17340 KB Output is correct
20 Correct 76 ms 17400 KB Output is correct
21 Correct 99 ms 17240 KB Output is correct
22 Correct 81 ms 17448 KB Output is correct
23 Correct 79 ms 17328 KB Output is correct
24 Correct 76 ms 17512 KB Output is correct
25 Correct 1649 ms 197344 KB Output is correct
26 Correct 1280 ms 225712 KB Output is correct
27 Correct 1212 ms 202488 KB Output is correct
28 Correct 1152 ms 213444 KB Output is correct
29 Correct 1284 ms 177240 KB Output is correct
30 Correct 1253 ms 186208 KB Output is correct
31 Correct 1452 ms 235768 KB Output is correct
32 Correct 10 ms 5020 KB Output is correct
33 Correct 110 ms 19864 KB Output is correct
34 Correct 79 ms 18712 KB Output is correct
35 Correct 82 ms 18696 KB Output is correct
36 Correct 2 ms 504 KB Output is correct
37 Correct 98 ms 18748 KB Output is correct
38 Correct 102 ms 18492 KB Output is correct
39 Correct 76 ms 18500 KB Output is correct
40 Correct 93 ms 18444 KB Output is correct
41 Correct 77 ms 18612 KB Output is correct
42 Correct 94 ms 18500 KB Output is correct
43 Correct 84 ms 18600 KB Output is correct
44 Correct 1680 ms 214156 KB Output is correct
45 Correct 1308 ms 259932 KB Output is correct
46 Correct 1193 ms 236704 KB Output is correct
47 Correct 1154 ms 226888 KB Output is correct
48 Correct 1340 ms 191136 KB Output is correct
49 Correct 1281 ms 200028 KB Output is correct
50 Correct 1489 ms 236976 KB Output is correct
51 Runtime error 1256 ms 451632 KB Execution killed with signal 6
52 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4428 KB Output is correct
2 Correct 107 ms 18632 KB Output is correct
3 Correct 94 ms 17512 KB Output is correct
4 Correct 85 ms 17604 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 79 ms 17644 KB Output is correct
7 Correct 9 ms 4428 KB Output is correct
8 Correct 108 ms 18700 KB Output is correct
9 Correct 80 ms 17476 KB Output is correct
10 Correct 80 ms 17596 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 76 ms 17640 KB Output is correct
13 Correct 87 ms 17448 KB Output is correct
14 Correct 80 ms 17368 KB Output is correct
15 Correct 100 ms 17208 KB Output is correct
16 Correct 74 ms 17348 KB Output is correct
17 Correct 75 ms 17324 KB Output is correct
18 Correct 75 ms 17472 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 292 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4428 KB Output is correct
2 Correct 107 ms 18632 KB Output is correct
3 Correct 94 ms 17512 KB Output is correct
4 Correct 85 ms 17604 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 79 ms 17644 KB Output is correct
7 Correct 9 ms 4428 KB Output is correct
8 Correct 108 ms 18700 KB Output is correct
9 Correct 80 ms 17476 KB Output is correct
10 Correct 80 ms 17596 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 76 ms 17640 KB Output is correct
13 Correct 87 ms 17448 KB Output is correct
14 Correct 80 ms 17368 KB Output is correct
15 Correct 100 ms 17208 KB Output is correct
16 Correct 74 ms 17348 KB Output is correct
17 Correct 75 ms 17324 KB Output is correct
18 Correct 75 ms 17472 KB Output is correct
19 Correct 9 ms 4428 KB Output is correct
20 Correct 108 ms 18680 KB Output is correct
21 Correct 78 ms 17460 KB Output is correct
22 Correct 85 ms 17608 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 74 ms 17580 KB Output is correct
25 Correct 87 ms 17340 KB Output is correct
26 Correct 76 ms 17400 KB Output is correct
27 Correct 99 ms 17240 KB Output is correct
28 Correct 81 ms 17448 KB Output is correct
29 Correct 79 ms 17328 KB Output is correct
30 Correct 76 ms 17512 KB Output is correct
31 Correct 1649 ms 197344 KB Output is correct
32 Correct 1280 ms 225712 KB Output is correct
33 Correct 1212 ms 202488 KB Output is correct
34 Correct 1152 ms 213444 KB Output is correct
35 Correct 1284 ms 177240 KB Output is correct
36 Correct 1253 ms 186208 KB Output is correct
37 Correct 1452 ms 235768 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Incorrect 1 ms 292 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4428 KB Output is correct
2 Correct 107 ms 18632 KB Output is correct
3 Correct 94 ms 17512 KB Output is correct
4 Correct 85 ms 17604 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 79 ms 17644 KB Output is correct
7 Correct 9 ms 4428 KB Output is correct
8 Correct 108 ms 18700 KB Output is correct
9 Correct 80 ms 17476 KB Output is correct
10 Correct 80 ms 17596 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 76 ms 17640 KB Output is correct
13 Correct 87 ms 17448 KB Output is correct
14 Correct 80 ms 17368 KB Output is correct
15 Correct 100 ms 17208 KB Output is correct
16 Correct 74 ms 17348 KB Output is correct
17 Correct 75 ms 17324 KB Output is correct
18 Correct 75 ms 17472 KB Output is correct
19 Correct 9 ms 4428 KB Output is correct
20 Correct 108 ms 18680 KB Output is correct
21 Correct 78 ms 17460 KB Output is correct
22 Correct 85 ms 17608 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 74 ms 17580 KB Output is correct
25 Correct 87 ms 17340 KB Output is correct
26 Correct 76 ms 17400 KB Output is correct
27 Correct 99 ms 17240 KB Output is correct
28 Correct 81 ms 17448 KB Output is correct
29 Correct 79 ms 17328 KB Output is correct
30 Correct 76 ms 17512 KB Output is correct
31 Correct 1649 ms 197344 KB Output is correct
32 Correct 1280 ms 225712 KB Output is correct
33 Correct 1212 ms 202488 KB Output is correct
34 Correct 1152 ms 213444 KB Output is correct
35 Correct 1284 ms 177240 KB Output is correct
36 Correct 1253 ms 186208 KB Output is correct
37 Correct 1452 ms 235768 KB Output is correct
38 Correct 10 ms 5020 KB Output is correct
39 Correct 110 ms 19864 KB Output is correct
40 Correct 79 ms 18712 KB Output is correct
41 Correct 82 ms 18696 KB Output is correct
42 Correct 2 ms 504 KB Output is correct
43 Correct 98 ms 18748 KB Output is correct
44 Correct 102 ms 18492 KB Output is correct
45 Correct 76 ms 18500 KB Output is correct
46 Correct 93 ms 18444 KB Output is correct
47 Correct 77 ms 18612 KB Output is correct
48 Correct 94 ms 18500 KB Output is correct
49 Correct 84 ms 18600 KB Output is correct
50 Correct 1680 ms 214156 KB Output is correct
51 Correct 1308 ms 259932 KB Output is correct
52 Correct 1193 ms 236704 KB Output is correct
53 Correct 1154 ms 226888 KB Output is correct
54 Correct 1340 ms 191136 KB Output is correct
55 Correct 1281 ms 200028 KB Output is correct
56 Correct 1489 ms 236976 KB Output is correct
57 Runtime error 1256 ms 451632 KB Execution killed with signal 6
58 Halted 0 ms 0 KB -