Submission #1167459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167459		nai0610	Through Another Maze Darkly (CCO21_day1problem3)	C++20	4 / 25	9109 ms	589408 KiB

Main

#include <bits/stdc++.h>
#define ll unsigned long long
#define ld long double
using namespace std;
// 
const int maxn =8e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int n,q,cur[maxn];
ll b[maxn];
vector<int> g[maxn];
vector<ll> a[maxn];
int main() {
    //freopen("MAZE.inp","r",stdin);
    //freopen("MAZE.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t start,end;
	start=clock();
	cin >>n>>q;
	for (int i=1;i<=n;i++) {
		int k;
		cin >>k;
		g[i].resize(k);
		a[i].resize(k);
		for (int j=0;j<k;j++) cin >>g[i][j];
	}
	ll s=0;
	for (int i=1;i<=n;i++) {
		for (int j=0;j<g[i].size();j++) a[i][j]=rd();
		s^=a[i][0];
	}
	for (int i=1;i<=n;i++) b[i]=rd();
	int u=1;
	ll val=b[u];
	s^=val;
	vector<int> pos={u};
	map<ll,int> m;
	m[s]=0;
	int pre0=-1,pre1=-1;
	while (1) {
		int k=g[u].size();
		s^=a[u][cur[u]];
		int nex=g[u][(cur[u]+1)%k];
		(cur[u]+=1)%=k;
		s^=a[u][cur[u]];
		s^=val;
		val=b[nex];
		s^=val;
		u=nex;
		pos.push_back(u);
		int cnt=pos.size()-1;
		if (m.find(s)!=m.end()){
			pre0=m[s];
			pre1=cnt;
			break;
		}
		m[s]=cnt;
	}
	while (q--) {
		ll k;
		cin >>k;
		if (k<pre0) cout <<pos[k]<<'\n';
		else cout <<pos[pre0+(k-pre0)%(pre1-pre0)]<<'\n';
	}
	end=clock();
	ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L);
	cerr<<dur<<'\n';
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 12
• Subtask 4: 0 / 5