Submission #936241

#	Time	Username	Problem	Language	Result	Execution time	Memory
936241		Baizho	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1033 ms	429144 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(2e5)+100;
const int M = ll(2e5) + 100;
const long long inf = 5e18;
//const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
 
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
 
int n, m, q, dis[N], del[N], block, lpos[N], used[N];
vector<int> gr[N], pos[N];
vector<pair<int, int> > save[N];

void calc(int r, int id) {
	int p = 0;
	for(int i = 1; i <= r; i ++) {
		dis[i] = 0;
		for(auto to : gr[i]) {
			dis[i] = max(dis[to] + 1, dis[i]);
		}
		if(del[i] == id) {
			if(dis[i] == 0) dis[i] = -1;
		}  
	}
}

void Baizho() {
	cin>>n>>m>>q;
	block = 320;
	for(int i = 1; i <= m; i ++) {
		int u, v; cin>>u>>v;
		// reverse need so we can have ideas of reverse like max distance from party to people where town_party >= town_people
		gr[v].pb(u);
	} 
	for(int i = 1; i <= n; i ++) {
		int mx = -1;
		for(auto to : gr[i]) {
			if(save[to].size()) {
				auto x = save[to][0];
				pos[x.ff].pb(to);
				lpos[to] = 0;
				mx = max(mx, x.ff);
			}
		}
		for(int j = mx; j >= 0 && save[i].size() < block;) {
			int to = pos[j].back();
			int p = lpos[to];
//			cout<<j<<" "<<i<<" "<<to<<" "<<p<<" yolo "<<endl;
			if(used[save[to][p].ss] != i) {
				save[i].pb({save[to][p].ff + 1, save[to][p].ss});
				used[save[to][p].ss] = i;
			}
			pos[j].pop_back();
			if(p + 1 < save[to].size()) {
				pos[save[to][p + 1].ff].pb(to);
				lpos[to] = p + 1;
			}
			if(pos[j].empty()) j --;
		}
		for(auto to : gr[i]) {
			if(lpos[to] < save[to].size()) {
				pos[save[to][lpos[to]].ff].clear();
			}
		}
		if(save[i].size() < block) save[i].pb({0, i});
//		cout<<i<<endl;
//		for(auto x : save[i]) cout<<x.ff<<" "<<x.ss<<endl;
	}
	for(int i = 1; i <= q; i ++) {
		int t, y; cin>>t>>y;
		for(int j = 0; j < y; j ++) {
			int c; cin>>c;
			del[c] = i;
		}
		if(y >= block) {
			calc(t, i);
			cout<<dis[t]<<"\n";
			continue;
		}
		int res = -1;
		for(int j = 0; j < save[t].size(); j ++) {
			if(del[save[t][j].ss] != i) {
				res = save[t][j].ff;
				break;
			}
		}
		cout<<res<<"\n";
	}
}
 
signed main() {		
// 	Freopen("nondec");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;
 
    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message (stderr)

bitaro.cpp: In function 'void calc(int, int)':
bitaro.cpp:42:6: warning: unused variable 'p' [-Wunused-variable]
   42 |  int p = 0;
      |      ^
bitaro.cpp: In function 'void Baizho()':
bitaro.cpp:72:44: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |   for(int j = mx; j >= 0 && save[i].size() < block;) {
      |                             ~~~~~~~~~~~~~~~^~~~~~~
bitaro.cpp:81:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    if(p + 1 < save[to].size()) {
      |       ~~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    if(lpos[to] < save[to].size()) {
      |       ~~~~~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:92:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |   if(save[i].size() < block) save[i].pb({0, i});
      |      ~~~~~~~~~~~~~~~^~~~~~~
bitaro.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for(int j = 0; j < save[t].size(); j ++) {
      |                  ~~^~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void Freopen(std::string)':
bitaro.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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