oj.uz

Submission #95061

# Submission time Handle Problem Language Result Execution time Memory
95061 2019-01-27T07:34:14 Z hamid Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 234872 KB 
#include<bits/stdc++.h>

using namespace std;

typedef int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;

#define RETD(x) cout << fixed << setprecision(15) << x;
#define X first
#define Y second
#define PB push_back
#define For(i,a,b) for(ll i=a;i<b;i++)
#define SZ(x) ((ll)(x.size()))
#define smax(a,b) a=max(a,b)
#define ER(x) cout << #x << ' ' << x << '\n'
#define MKP make_pair
#define smin(a,b) a=min(a,b);

const ll M=1e5+5,inf=1e9,SM=340;

typedef complex<ld> point;

pair<ld,point> p[M];

ll n,m,q;
vector<pll> dp[M];
ll res[M];
vector<ll> g[M];

void merg(ll x,ll y){
  for(pll f:dp[x]){
    res[f.Y]=f.X;
  }
  for(pll f:dp[y]){
    smin(res[f.Y],f.X-1);
  }
  For(i,0,SZ(dp[x])){
    dp[x][i].X=res[dp[x][i].Y];
    res[dp[x][i].Y]=0;
  }
  For(i,0,SZ(dp[y])){
    if (res[dp[y][i].Y]){
      dp[x].PB({dp[y][i].X-1,dp[y][i].Y});
      res[dp[y][i].Y]=0;
    }
  }
  sort(dp[x].begin(),dp[x].end());
  while (SZ(dp[x])>SM) dp[x].pop_back();
}

vll qud;
ll mark[M];
ll tmp[M];

int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m >> q;
  For(i,0,m){
    ll u,v;
    cin >> u >> v;
    u--;v--;
    g[v].PB(u);
  }
  For(x,0,n){
    //ER(x);
    for (ll y:g[x]){
      //ER(y);
      merg(x,y);
    }
    if (SZ(dp[x])<SM){
      dp[x].PB({0,x});
    }
  }
  while (q--){
    //ER(q);
    ll v,c;
    cin >> v >> c;
    v--;
    For(i,0,c){
      ll x;
      cin >> x;
      x--;
      qud.PB(x);
      mark[x]=1;
    }
    if (c<SM){
      bool ah=0;
      for (pll x:dp[v]){
	//ER(x.Y << ' ' << mark[x.Y]);
	if (!mark[x.Y]){
	  cout << -x.X << '\n';
	  ah=1;
	  break;
	}
      }
      if (!ah) cout << "-1\n";
    }else{
      For(i,0,v+1){
	tmp[i]=0;
	if (mark[i]){
	  tmp[i]=-1;
	}
	for (ll y:g[i]){
	  if (tmp[y]==-1) continue;
	  smax(tmp[i],tmp[y]+1);
	}
      }
      cout << tmp[v] << '\n';
    }
    for (ll f:qud){
      mark[f]=0;
    }
    qud.clear();
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 8 ms 5468 KB Output is correct
6 Correct 10 ms 5624 KB Output is correct
7 Correct 8 ms 5496 KB Output is correct
8 Correct 19 ms 8412 KB Output is correct
9 Correct 20 ms 8440 KB Output is correct
10 Correct 19 ms 8440 KB Output is correct
11 Correct 19 ms 8184 KB Output is correct
12 Correct 14 ms 6392 KB Output is correct
13 Correct 17 ms 7800 KB Output is correct
14 Correct 18 ms 7032 KB Output is correct
15 Correct 14 ms 6008 KB Output is correct
16 Correct 17 ms 7160 KB Output is correct
17 Correct 18 ms 7288 KB Output is correct
18 Correct 14 ms 6264 KB Output is correct
19 Correct 18 ms 7288 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 8 ms 5468 KB Output is correct
6 Correct 10 ms 5624 KB Output is correct
7 Correct 8 ms 5496 KB Output is correct
8 Correct 19 ms 8412 KB Output is correct
9 Correct 20 ms 8440 KB Output is correct
10 Correct 19 ms 8440 KB Output is correct
11 Correct 19 ms 8184 KB Output is correct
12 Correct 14 ms 6392 KB Output is correct
13 Correct 17 ms 7800 KB Output is correct
14 Correct 18 ms 7032 KB Output is correct
15 Correct 14 ms 6008 KB Output is correct
16 Correct 17 ms 7160 KB Output is correct
17 Correct 18 ms 7288 KB Output is correct
18 Correct 14 ms 6264 KB Output is correct
19 Correct 18 ms 7288 KB Output is correct
20 Correct 796 ms 9684 KB Output is correct
21 Correct 795 ms 9592 KB Output is correct
22 Correct 809 ms 9612 KB Output is correct
23 Correct 915 ms 9628 KB Output is correct
24 Execution timed out 2060 ms 234872 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 8 ms 5468 KB Output is correct
6 Correct 10 ms 5624 KB Output is correct
7 Correct 8 ms 5496 KB Output is correct
8 Correct 19 ms 8412 KB Output is correct
9 Correct 20 ms 8440 KB Output is correct
10 Correct 19 ms 8440 KB Output is correct
11 Correct 19 ms 8184 KB Output is correct
12 Correct 14 ms 6392 KB Output is correct
13 Correct 17 ms 7800 KB Output is correct
14 Correct 18 ms 7032 KB Output is correct
15 Correct 14 ms 6008 KB Output is correct
16 Correct 17 ms 7160 KB Output is correct
17 Correct 18 ms 7288 KB Output is correct
18 Correct 14 ms 6264 KB Output is correct
19 Correct 18 ms 7288 KB Output is correct
20 Correct 796 ms 9684 KB Output is correct
21 Correct 795 ms 9592 KB Output is correct
22 Correct 809 ms 9612 KB Output is correct
23 Correct 915 ms 9628 KB Output is correct
24 Execution timed out 2060 ms 234872 KB Time limit exceeded
25 Halted 0 ms 0 KB -