oj.uz

Submission #402569

# Submission time Handle Problem Language Result Execution time Memory
402569 2021-05-12T00:51:37 Z rrrr10000 From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 223280 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 56 ms 4556 KB Output is correct
2 Correct 82 ms 18664 KB Output is correct
3 Correct 82 ms 17668 KB Output is correct
4 Correct 122 ms 17736 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 84 ms 17700 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 82 ms 18580 KB Output is correct
3 Correct 83 ms 17668 KB Output is correct
4 Correct 124 ms 17736 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 83 ms 17684 KB Output is correct
7 Correct 77 ms 17560 KB Output is correct
8 Correct 77 ms 17488 KB Output is correct
9 Correct 72 ms 17296 KB Output is correct
10 Correct 102 ms 17800 KB Output is correct
11 Correct 90 ms 17568 KB Output is correct
12 Correct 81 ms 17632 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 82 ms 18580 KB Output is correct
3 Correct 83 ms 17668 KB Output is correct
4 Correct 124 ms 17736 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 83 ms 17684 KB Output is correct
7 Correct 77 ms 17560 KB Output is correct
8 Correct 77 ms 17488 KB Output is correct
9 Correct 72 ms 17296 KB Output is correct
10 Correct 102 ms 17800 KB Output is correct
11 Correct 90 ms 17568 KB Output is correct
12 Correct 81 ms 17632 KB Output is correct
13 Correct 57 ms 4556 KB Output is correct
14 Correct 84 ms 18664 KB Output is correct
15 Correct 81 ms 17700 KB Output is correct
16 Correct 135 ms 17864 KB Output is correct
17 Correct 3 ms 332 KB Output is correct
18 Correct 84 ms 17704 KB Output is correct
19 Correct 82 ms 17604 KB Output is correct
20 Correct 77 ms 17476 KB Output is correct
21 Correct 75 ms 17348 KB Output is correct
22 Correct 101 ms 17744 KB Output is correct
23 Correct 84 ms 17576 KB Output is correct
24 Correct 80 ms 17616 KB Output is correct
25 Correct 1398 ms 198844 KB Output is correct
26 Correct 1359 ms 223280 KB Output is correct
27 Correct 1244 ms 198964 KB Output is correct
28 Correct 961 ms 209496 KB Output is correct
29 Execution timed out 6043 ms 174364 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 82 ms 18580 KB Output is correct
3 Correct 83 ms 17668 KB Output is correct
4 Correct 124 ms 17736 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 83 ms 17684 KB Output is correct
7 Correct 77 ms 17560 KB Output is correct
8 Correct 77 ms 17488 KB Output is correct
9 Correct 72 ms 17296 KB Output is correct
10 Correct 102 ms 17800 KB Output is correct
11 Correct 90 ms 17568 KB Output is correct
12 Correct 81 ms 17632 KB Output is correct
13 Correct 57 ms 4556 KB Output is correct
14 Correct 84 ms 18664 KB Output is correct
15 Correct 81 ms 17700 KB Output is correct
16 Correct 135 ms 17864 KB Output is correct
17 Correct 3 ms 332 KB Output is correct
18 Correct 84 ms 17704 KB Output is correct
19 Correct 82 ms 17604 KB Output is correct
20 Correct 77 ms 17476 KB Output is correct
21 Correct 75 ms 17348 KB Output is correct
22 Correct 101 ms 17744 KB Output is correct
23 Correct 84 ms 17576 KB Output is correct
24 Correct 80 ms 17616 KB Output is correct
25 Correct 1398 ms 198844 KB Output is correct
26 Correct 1359 ms 223280 KB Output is correct
27 Correct 1244 ms 198964 KB Output is correct
28 Correct 961 ms 209496 KB Output is correct
29 Execution timed out 6043 ms 174364 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4556 KB Output is correct
2 Correct 82 ms 18664 KB Output is correct
3 Correct 82 ms 17668 KB Output is correct
4 Correct 122 ms 17736 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 84 ms 17700 KB Output is correct
7 Correct 56 ms 4556 KB Output is correct
8 Correct 82 ms 18580 KB Output is correct
9 Correct 83 ms 17668 KB Output is correct
10 Correct 124 ms 17736 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 83 ms 17684 KB Output is correct
13 Correct 77 ms 17560 KB Output is correct
14 Correct 77 ms 17488 KB Output is correct
15 Correct 72 ms 17296 KB Output is correct
16 Correct 102 ms 17800 KB Output is correct
17 Correct 90 ms 17568 KB Output is correct
18 Correct 81 ms 17632 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 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4556 KB Output is correct
2 Correct 82 ms 18664 KB Output is correct
3 Correct 82 ms 17668 KB Output is correct
4 Correct 122 ms 17736 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 84 ms 17700 KB Output is correct
7 Correct 56 ms 4556 KB Output is correct
8 Correct 82 ms 18580 KB Output is correct
9 Correct 83 ms 17668 KB Output is correct
10 Correct 124 ms 17736 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 83 ms 17684 KB Output is correct
13 Correct 77 ms 17560 KB Output is correct
14 Correct 77 ms 17488 KB Output is correct
15 Correct 72 ms 17296 KB Output is correct
16 Correct 102 ms 17800 KB Output is correct
17 Correct 90 ms 17568 KB Output is correct
18 Correct 81 ms 17632 KB Output is correct
19 Correct 57 ms 4556 KB Output is correct
20 Correct 84 ms 18664 KB Output is correct
21 Correct 81 ms 17700 KB Output is correct
22 Correct 135 ms 17864 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 84 ms 17704 KB Output is correct
25 Correct 82 ms 17604 KB Output is correct
26 Correct 77 ms 17476 KB Output is correct
27 Correct 75 ms 17348 KB Output is correct
28 Correct 101 ms 17744 KB Output is correct
29 Correct 84 ms 17576 KB Output is correct
30 Correct 80 ms 17616 KB Output is correct
31 Correct 1398 ms 198844 KB Output is correct
32 Correct 1359 ms 223280 KB Output is correct
33 Correct 1244 ms 198964 KB Output is correct
34 Correct 961 ms 209496 KB Output is correct
35 Execution timed out 6043 ms 174364 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4556 KB Output is correct
2 Correct 82 ms 18664 KB Output is correct
3 Correct 82 ms 17668 KB Output is correct
4 Correct 122 ms 17736 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 84 ms 17700 KB Output is correct
7 Correct 56 ms 4556 KB Output is correct
8 Correct 82 ms 18580 KB Output is correct
9 Correct 83 ms 17668 KB Output is correct
10 Correct 124 ms 17736 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 83 ms 17684 KB Output is correct
13 Correct 77 ms 17560 KB Output is correct
14 Correct 77 ms 17488 KB Output is correct
15 Correct 72 ms 17296 KB Output is correct
16 Correct 102 ms 17800 KB Output is correct
17 Correct 90 ms 17568 KB Output is correct
18 Correct 81 ms 17632 KB Output is correct
19 Correct 57 ms 4556 KB Output is correct
20 Correct 84 ms 18664 KB Output is correct
21 Correct 81 ms 17700 KB Output is correct
22 Correct 135 ms 17864 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 84 ms 17704 KB Output is correct
25 Correct 82 ms 17604 KB Output is correct
26 Correct 77 ms 17476 KB Output is correct
27 Correct 75 ms 17348 KB Output is correct
28 Correct 101 ms 17744 KB Output is correct
29 Correct 84 ms 17576 KB Output is correct
30 Correct 80 ms 17616 KB Output is correct
31 Correct 1398 ms 198844 KB Output is correct
32 Correct 1359 ms 223280 KB Output is correct
33 Correct 1244 ms 198964 KB Output is correct
34 Correct 961 ms 209496 KB Output is correct
35 Execution timed out 6043 ms 174364 KB Time limit exceeded
36 Halted 0 ms 0 KB -