Submission #757564

#	Time	Username	Problem	Language	Result	Execution time	Memory
757564		mgl_diamond	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2053 ms	416480 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l; i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define pb push_back
#define se second

const int N = 1e5+5;
const int INF = 1e9;
int SIZE;

int n, m, q;

bool allow[N], used[N];
int block[N];
vector<ii> best[N];
vector<int> graph[N], adj[N];

void prep() {
	for(int i=1;i<=n;i++){
		for(int x:graph[i]){
			vector<ii>fin;
			best[x].push_back({0,x});
			//duplicates are dangerous
			//remove duplicates while doing merge sort
			int a = 0,b=0;
			int sa = sz(best[x]);
			int sb = sz(best[i]);
			while(sz(fin)<SIZE  && (a<sa || b < sb)){
				if(b == sb ||  (a!=sa && best[x][a].fi+1 >= best[i][b].fi)){
					best[x][a].fi++;
					fin.pb(best[x][a]);
					used[best[x][a].se] = 1;
					
					best[x][a].fi--;
					a++;
				}else{
					fin.pb(best[i][b]);
					used[best[i][b].se] = 1;
					b++;
				}
				while(a<sa && used[best[x][a].se])a++;
				while(b<sb && used[best[i][b].se])b++;
			}
			best[x].pop_back();
			for(auto z:fin) used[z.se] = 0;
			swap(best[i],fin);
		}
	}
}

int dp[N];

void solve() {
  cin >> n >> m >> q;
  SIZE = 350;

  for(int i=0; i<m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    graph[v].push_back(u);
  }

  fill(allow, allow+n+1, 1);
  prep();

  for(int t=0; t<q; ++t) {
    int s, c;
    cin >> s >> c;

    for(int j=0; j<c; ++j) {
      cin >> block[j];
      allow[block[j]] = 0;
    }

    int ans = -1;
    if (s < SIZE) {
      bool found = 0;
      for(auto cand : best[s]) if (allow[cand.se]) {
        ans = cand.fi;
        found = 1;
        break;
      }
      if (allow[s]) ans = max(ans, 0);
    }
    else {
      for(int i=1; i<=n; ++i) 
        dp[i] = -1;

      dp[s] = 0;
      if (allow[s]) ans = 0;
      
      for(int i=s-1; i>0; --i) {
        for(int x : adj[i]) if (dp[x] != -1)
          dp[i] = max(dp[i], dp[x] + 1);
        if (allow[i]) ans = max(ans, dp[i]);
      }
    }

    cout << ans << "\n";

    for(int j=0; j<c; ++j) {
      allow[block[j]] = 1;
    }
  }

  // for(int i=1; i<=n; ++i) {
  //   cout << "From " << i << " Has " << best[i].size() << " Choices: \n";
  //   for(auto v : best[i]) cout << "Vertice " << v.fi << " Dist " << v.se << "\n";
  //   cout << "------------\n";
  // }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  if (fopen("input.inp", "r")) {
    freopen("input.inp", "r", stdin);
    freopen("input.out", "w", stdout);
  }

  solve();
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:85:12: warning: variable 'found' set but not used [-Wunused-but-set-variable]
   85 |       bool found = 0;
      |            ^~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     freopen("input.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86