oj.uz

답안 #402237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402237 2021-05-11T12:56:05 Z rrrr10000 From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 1226 ms 400376 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<=500000);
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4940 KB Output is correct
2 Correct 101 ms 19256 KB Output is correct
3 Correct 77 ms 18060 KB Output is correct
4 Correct 84 ms 18048 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 83 ms 18148 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4940 KB Output is correct
2 Correct 102 ms 19228 KB Output is correct
3 Correct 88 ms 18064 KB Output is correct
4 Correct 83 ms 18092 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 100 ms 18208 KB Output is correct
7 Correct 92 ms 17952 KB Output is correct
8 Correct 80 ms 17832 KB Output is correct
9 Correct 102 ms 17708 KB Output is correct
10 Correct 83 ms 17936 KB Output is correct
11 Correct 75 ms 17920 KB Output is correct
12 Correct 84 ms 18036 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4940 KB Output is correct
2 Correct 102 ms 19228 KB Output is correct
3 Correct 88 ms 18064 KB Output is correct
4 Correct 83 ms 18092 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 100 ms 18208 KB Output is correct
7 Correct 92 ms 17952 KB Output is correct
8 Correct 80 ms 17832 KB Output is correct
9 Correct 102 ms 17708 KB Output is correct
10 Correct 83 ms 17936 KB Output is correct
11 Correct 75 ms 17920 KB Output is correct
12 Correct 84 ms 18036 KB Output is correct
13 Correct 12 ms 4940 KB Output is correct
14 Correct 117 ms 19256 KB Output is correct
15 Correct 106 ms 18084 KB Output is correct
16 Correct 100 ms 18100 KB Output is correct
17 Correct 2 ms 500 KB Output is correct
18 Correct 82 ms 18148 KB Output is correct
19 Correct 91 ms 17860 KB Output is correct
20 Correct 80 ms 17804 KB Output is correct
21 Correct 95 ms 17760 KB Output is correct
22 Correct 75 ms 17852 KB Output is correct
23 Correct 100 ms 17876 KB Output is correct
24 Correct 78 ms 18048 KB Output is correct
25 Runtime error 1226 ms 400376 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4940 KB Output is correct
2 Correct 102 ms 19228 KB Output is correct
3 Correct 88 ms 18064 KB Output is correct
4 Correct 83 ms 18092 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 100 ms 18208 KB Output is correct
7 Correct 92 ms 17952 KB Output is correct
8 Correct 80 ms 17832 KB Output is correct
9 Correct 102 ms 17708 KB Output is correct
10 Correct 83 ms 17936 KB Output is correct
11 Correct 75 ms 17920 KB Output is correct
12 Correct 84 ms 18036 KB Output is correct
13 Correct 12 ms 4940 KB Output is correct
14 Correct 117 ms 19256 KB Output is correct
15 Correct 106 ms 18084 KB Output is correct
16 Correct 100 ms 18100 KB Output is correct
17 Correct 2 ms 500 KB Output is correct
18 Correct 82 ms 18148 KB Output is correct
19 Correct 91 ms 17860 KB Output is correct
20 Correct 80 ms 17804 KB Output is correct
21 Correct 95 ms 17760 KB Output is correct
22 Correct 75 ms 17852 KB Output is correct
23 Correct 100 ms 17876 KB Output is correct
24 Correct 78 ms 18048 KB Output is correct
25 Runtime error 1226 ms 400376 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4940 KB Output is correct
2 Correct 101 ms 19256 KB Output is correct
3 Correct 77 ms 18060 KB Output is correct
4 Correct 84 ms 18048 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 83 ms 18148 KB Output is correct
7 Correct 9 ms 4940 KB Output is correct
8 Correct 102 ms 19228 KB Output is correct
9 Correct 88 ms 18064 KB Output is correct
10 Correct 83 ms 18092 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 100 ms 18208 KB Output is correct
13 Correct 92 ms 17952 KB Output is correct
14 Correct 80 ms 17832 KB Output is correct
15 Correct 102 ms 17708 KB Output is correct
16 Correct 83 ms 17936 KB Output is correct
17 Correct 75 ms 17920 KB Output is correct
18 Correct 84 ms 18036 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 268 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4940 KB Output is correct
2 Correct 101 ms 19256 KB Output is correct
3 Correct 77 ms 18060 KB Output is correct
4 Correct 84 ms 18048 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 83 ms 18148 KB Output is correct
7 Correct 9 ms 4940 KB Output is correct
8 Correct 102 ms 19228 KB Output is correct
9 Correct 88 ms 18064 KB Output is correct
10 Correct 83 ms 18092 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 100 ms 18208 KB Output is correct
13 Correct 92 ms 17952 KB Output is correct
14 Correct 80 ms 17832 KB Output is correct
15 Correct 102 ms 17708 KB Output is correct
16 Correct 83 ms 17936 KB Output is correct
17 Correct 75 ms 17920 KB Output is correct
18 Correct 84 ms 18036 KB Output is correct
19 Correct 12 ms 4940 KB Output is correct
20 Correct 117 ms 19256 KB Output is correct
21 Correct 106 ms 18084 KB Output is correct
22 Correct 100 ms 18100 KB Output is correct
23 Correct 2 ms 500 KB Output is correct
24 Correct 82 ms 18148 KB Output is correct
25 Correct 91 ms 17860 KB Output is correct
26 Correct 80 ms 17804 KB Output is correct
27 Correct 95 ms 17760 KB Output is correct
28 Correct 75 ms 17852 KB Output is correct
29 Correct 100 ms 17876 KB Output is correct
30 Correct 78 ms 18048 KB Output is correct
31 Runtime error 1226 ms 400376 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4940 KB Output is correct
2 Correct 101 ms 19256 KB Output is correct
3 Correct 77 ms 18060 KB Output is correct
4 Correct 84 ms 18048 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 83 ms 18148 KB Output is correct
7 Correct 9 ms 4940 KB Output is correct
8 Correct 102 ms 19228 KB Output is correct
9 Correct 88 ms 18064 KB Output is correct
10 Correct 83 ms 18092 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 100 ms 18208 KB Output is correct
13 Correct 92 ms 17952 KB Output is correct
14 Correct 80 ms 17832 KB Output is correct
15 Correct 102 ms 17708 KB Output is correct
16 Correct 83 ms 17936 KB Output is correct
17 Correct 75 ms 17920 KB Output is correct
18 Correct 84 ms 18036 KB Output is correct
19 Correct 12 ms 4940 KB Output is correct
20 Correct 117 ms 19256 KB Output is correct
21 Correct 106 ms 18084 KB Output is correct
22 Correct 100 ms 18100 KB Output is correct
23 Correct 2 ms 500 KB Output is correct
24 Correct 82 ms 18148 KB Output is correct
25 Correct 91 ms 17860 KB Output is correct
26 Correct 80 ms 17804 KB Output is correct
27 Correct 95 ms 17760 KB Output is correct
28 Correct 75 ms 17852 KB Output is correct
29 Correct 100 ms 17876 KB Output is correct
30 Correct 78 ms 18048 KB Output is correct
31 Runtime error 1226 ms 400376 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -