oj.uz

Submission #402571

# Submission time Handle Problem Language Result Execution time Memory
402571 2021-05-12T00:54:35 Z rrrr10000 From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 223044 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();
    vvp g(n);
    rep(i,m){
        ll a=readll()-1,b=readll()-1;
        g[a].pb(b,i);g[b].pb(a,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;
            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;
        }
    }


    vvi dis(n);
    rep(i,n)dis[i]=vi(len[i],inf);
    dis[0][0]=0;
    vi dis2(n,inf);
    SPQ(PP) pq;pq.emplace(0,0,0);
    while(!pq.empty()){
        ll cost,i,j;tie(cost,i,j)=pq.top();pq.pop();if(cost!=dis[i][j])continue;
        if(ngv[i]==(cost+1)%len[i]){
            for(auto x:g[i]){
                bool f=true;
                for(auto y:sp[i])if(x==y)f=false;
                if(!f)continue;
                ll nc=cost+1;
                if(ngv[x.fi]==nc%len[x.fi]){
                    if(ngv[x.fi]==(nc+len[i])%len[x.fi])nc=inf;
                    else nc+=len[i];
                }
                ll p=nc%len[x.fi];
                if(chmin(dis[x.fi][p],nc))pq.emplace(nc,x.fi,p);
            }
        }
        else/* if(chmin(dis2[i],cost))*/{
            for(auto x:g[i]){
                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))pq.emplace(nc,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];
            if(nge[x.se]==p0)continue;
            if(ngv[x.fi]==p1)continue;
            if(chmin(dis[x.fi][p1],cost+1))pq.emplace(cost+1,x.fi,p1);
        }
        ll p1=(cost+1)%len[i],p2=p1+1;if(p2>=len[i])p2-=len[i];
        if(ngv[i]==p1){
            bool ok=false,ok2=false;
            for(auto x:g[i]){
                bool f=true;
                for(auto y:sp[i])if(x==y)f=false;
                if(!f)continue;
                if(ngv[x.fi]!=(cost+1)%len[x.fi])ok=true;
                if(ngv[x.fi]!=(cost+len[i]+1)%len[x.fi])ok2=true;
            }
            ll nc;
            if(ok)nc=cost+2;
            else if(ok2)nc=cost+len[i]+2;
            else nc=inf;
            if(chmin(dis[i][p2],nc))pq.emplace(nc,i,p2);
        }
        else if(chmin(dis[i][p1],cost+1))pq.emplace(cost+1,i,p1);
    }
    // outvv(dis);
    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 57 ms 4556 KB Output is correct
2 Correct 84 ms 18572 KB Output is correct
3 Correct 80 ms 17664 KB Output is correct
4 Correct 129 ms 17788 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 82 ms 17676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4556 KB Output is correct
2 Correct 84 ms 18676 KB Output is correct
3 Correct 81 ms 17668 KB Output is correct
4 Correct 125 ms 17732 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 81 ms 17700 KB Output is correct
7 Correct 76 ms 17592 KB Output is correct
8 Correct 76 ms 17564 KB Output is correct
9 Correct 73 ms 17380 KB Output is correct
10 Correct 105 ms 17792 KB Output is correct
11 Correct 84 ms 17612 KB Output is correct
12 Correct 80 ms 17676 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4556 KB Output is correct
2 Correct 84 ms 18676 KB Output is correct
3 Correct 81 ms 17668 KB Output is correct
4 Correct 125 ms 17732 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 81 ms 17700 KB Output is correct
7 Correct 76 ms 17592 KB Output is correct
8 Correct 76 ms 17564 KB Output is correct
9 Correct 73 ms 17380 KB Output is correct
10 Correct 105 ms 17792 KB Output is correct
11 Correct 84 ms 17612 KB Output is correct
12 Correct 80 ms 17676 KB Output is correct
13 Correct 57 ms 4556 KB Output is correct
14 Correct 93 ms 18672 KB Output is correct
15 Correct 84 ms 17668 KB Output is correct
16 Correct 123 ms 17784 KB Output is correct
17 Correct 3 ms 332 KB Output is correct
18 Correct 83 ms 17732 KB Output is correct
19 Correct 86 ms 17512 KB Output is correct
20 Correct 77 ms 17548 KB Output is correct
21 Correct 83 ms 17448 KB Output is correct
22 Correct 98 ms 17772 KB Output is correct
23 Correct 84 ms 17516 KB Output is correct
24 Correct 79 ms 17652 KB Output is correct
25 Correct 1405 ms 198892 KB Output is correct
26 Correct 1326 ms 223044 KB Output is correct
27 Correct 1235 ms 198852 KB Output is correct
28 Correct 966 ms 209424 KB Output is correct
29 Execution timed out 6102 ms 174224 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4556 KB Output is correct
2 Correct 84 ms 18676 KB Output is correct
3 Correct 81 ms 17668 KB Output is correct
4 Correct 125 ms 17732 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 81 ms 17700 KB Output is correct
7 Correct 76 ms 17592 KB Output is correct
8 Correct 76 ms 17564 KB Output is correct
9 Correct 73 ms 17380 KB Output is correct
10 Correct 105 ms 17792 KB Output is correct
11 Correct 84 ms 17612 KB Output is correct
12 Correct 80 ms 17676 KB Output is correct
13 Correct 57 ms 4556 KB Output is correct
14 Correct 93 ms 18672 KB Output is correct
15 Correct 84 ms 17668 KB Output is correct
16 Correct 123 ms 17784 KB Output is correct
17 Correct 3 ms 332 KB Output is correct
18 Correct 83 ms 17732 KB Output is correct
19 Correct 86 ms 17512 KB Output is correct
20 Correct 77 ms 17548 KB Output is correct
21 Correct 83 ms 17448 KB Output is correct
22 Correct 98 ms 17772 KB Output is correct
23 Correct 84 ms 17516 KB Output is correct
24 Correct 79 ms 17652 KB Output is correct
25 Correct 1405 ms 198892 KB Output is correct
26 Correct 1326 ms 223044 KB Output is correct
27 Correct 1235 ms 198852 KB Output is correct
28 Correct 966 ms 209424 KB Output is correct
29 Execution timed out 6102 ms 174224 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4556 KB Output is correct
2 Correct 84 ms 18572 KB Output is correct
3 Correct 80 ms 17664 KB Output is correct
4 Correct 129 ms 17788 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 82 ms 17676 KB Output is correct
7 Correct 56 ms 4556 KB Output is correct
8 Correct 84 ms 18676 KB Output is correct
9 Correct 81 ms 17668 KB Output is correct
10 Correct 125 ms 17732 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 81 ms 17700 KB Output is correct
13 Correct 76 ms 17592 KB Output is correct
14 Correct 76 ms 17564 KB Output is correct
15 Correct 73 ms 17380 KB Output is correct
16 Correct 105 ms 17792 KB Output is correct
17 Correct 84 ms 17612 KB Output is correct
18 Correct 80 ms 17676 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 57 ms 4556 KB Output is correct
23 Correct 94 ms 18672 KB Output is correct
24 Correct 84 ms 17796 KB Output is correct
25 Correct 123 ms 17780 KB Output is correct
26 Correct 3 ms 332 KB Output is correct
27 Correct 84 ms 17724 KB Output is correct
28 Correct 77 ms 17604 KB Output is correct
29 Correct 79 ms 17548 KB Output is correct
30 Correct 75 ms 17312 KB Output is correct
31 Correct 101 ms 17800 KB Output is correct
32 Correct 84 ms 17548 KB Output is correct
33 Correct 78 ms 17668 KB Output is correct
34 Correct 1487 ms 203224 KB Output is correct
35 Correct 1469 ms 189452 KB Output is correct
36 Correct 1494 ms 189268 KB Output is correct
37 Correct 1343 ms 217104 KB Output is correct
38 Correct 1382 ms 198820 KB Output is correct
39 Execution timed out 6110 ms 173928 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4556 KB Output is correct
2 Correct 84 ms 18572 KB Output is correct
3 Correct 80 ms 17664 KB Output is correct
4 Correct 129 ms 17788 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 82 ms 17676 KB Output is correct
7 Correct 56 ms 4556 KB Output is correct
8 Correct 84 ms 18676 KB Output is correct
9 Correct 81 ms 17668 KB Output is correct
10 Correct 125 ms 17732 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 81 ms 17700 KB Output is correct
13 Correct 76 ms 17592 KB Output is correct
14 Correct 76 ms 17564 KB Output is correct
15 Correct 73 ms 17380 KB Output is correct
16 Correct 105 ms 17792 KB Output is correct
17 Correct 84 ms 17612 KB Output is correct
18 Correct 80 ms 17676 KB Output is correct
19 Correct 57 ms 4556 KB Output is correct
20 Correct 93 ms 18672 KB Output is correct
21 Correct 84 ms 17668 KB Output is correct
22 Correct 123 ms 17784 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 83 ms 17732 KB Output is correct
25 Correct 86 ms 17512 KB Output is correct
26 Correct 77 ms 17548 KB Output is correct
27 Correct 83 ms 17448 KB Output is correct
28 Correct 98 ms 17772 KB Output is correct
29 Correct 84 ms 17516 KB Output is correct
30 Correct 79 ms 17652 KB Output is correct
31 Correct 1405 ms 198892 KB Output is correct
32 Correct 1326 ms 223044 KB Output is correct
33 Correct 1235 ms 198852 KB Output is correct
34 Correct 966 ms 209424 KB Output is correct
35 Execution timed out 6102 ms 174224 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4556 KB Output is correct
2 Correct 84 ms 18572 KB Output is correct
3 Correct 80 ms 17664 KB Output is correct
4 Correct 129 ms 17788 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 82 ms 17676 KB Output is correct
7 Correct 56 ms 4556 KB Output is correct
8 Correct 84 ms 18676 KB Output is correct
9 Correct 81 ms 17668 KB Output is correct
10 Correct 125 ms 17732 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 81 ms 17700 KB Output is correct
13 Correct 76 ms 17592 KB Output is correct
14 Correct 76 ms 17564 KB Output is correct
15 Correct 73 ms 17380 KB Output is correct
16 Correct 105 ms 17792 KB Output is correct
17 Correct 84 ms 17612 KB Output is correct
18 Correct 80 ms 17676 KB Output is correct
19 Correct 57 ms 4556 KB Output is correct
20 Correct 93 ms 18672 KB Output is correct
21 Correct 84 ms 17668 KB Output is correct
22 Correct 123 ms 17784 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 83 ms 17732 KB Output is correct
25 Correct 86 ms 17512 KB Output is correct
26 Correct 77 ms 17548 KB Output is correct
27 Correct 83 ms 17448 KB Output is correct
28 Correct 98 ms 17772 KB Output is correct
29 Correct 84 ms 17516 KB Output is correct
30 Correct 79 ms 17652 KB Output is correct
31 Correct 1405 ms 198892 KB Output is correct
32 Correct 1326 ms 223044 KB Output is correct
33 Correct 1235 ms 198852 KB Output is correct
34 Correct 966 ms 209424 KB Output is correct
35 Execution timed out 6102 ms 174224 KB Time limit exceeded
36 Halted 0 ms 0 KB -