Submission #1284321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284321		muhammad-mutahir	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	176 ms	9016 KiB

incursion

#include <bits/stdc++.h>
using namespace std;
#include <vector>
#include "incursion.h"
#include <cstdio>

vector<int> mark(vector<pair<int, int>> F, int safe) {
  int N = F.size()+1;
  vector<int>deg(N+1,0);
  vector<vector<int>>adj(N+1);
  for(auto i:F){
  	adj[i.first].push_back(i.second);
  	adj[i.second].push_back(i.first);  	
  	deg[i.first]++;
  	deg[i.second]++;
  }
  queue<int>Q;
  Q.push(safe);
  vector<int>vis(N,0);
  vis[safe-1] = 2;
  vector<int>dis(N+1,1e9);
  dis[safe] = 0;
  int c = 2;
  while(Q.size()){
  	int x = Q.front();
  	Q.pop();
  	for(int i:adj[x]){
  		if(dis[i] > dis[x]+1){
  			dis[i] = dis[x]+1;
  			Q.push(i);
  		}
  	}
  }
  map<int,vector<int>>dd;
  for(int i = 1;i<=N;i++){
  	dd[dis[i]].push_back(i);
  }
  for(auto i:dd){
  	if(i.first == 0)continue;
  	for(auto j:i.second){
  		vis[j-1] = c;
  	}
  	c--;
  	c+=3;
  	c%=3;
  }

    
  return vis;
}

// int ans;
// vector<int>an;
// int visit(int c){
	// // vector<int>ck = {0,1,2,2};
	// // cout<<c<<endl;
	// ans = c;
	// c--;
	// return an[c];
// }
void locate(vector<pair<int, int>> F, int curr, int t) {
 int N = F.size()+1;
  vector<int>deg(N+1,0);
  vector<vector<int>>adj(N+1);
  for(auto i:F){
  	adj[i.first].push_back(i.second);
  	adj[i.second].push_back(i.first);  	
  	deg[i.first]++;
  	deg[i.second]++;
  }
  queue<int>Q;
  vector<int>viss(N+1,0);

  if(deg[curr] == 1){
  	t = visit(adj[curr][0]);
  	curr = adj[curr][0];
  }

  int c1 = visit(adj[curr][0]);
  int c = visit(curr);
  int c2 = visit(adj[curr][1]);
  int pv = visit(curr);
  // cout<<c<<" "<<c1<<" "<<c2<<endl;
  if(c == c1 and c == c2 and c2 == c1 and c == 2){
  	return;
  }

  int cr;
  if(c1 == 0 and c == 1 and c2 == 2){
  	Q.push(adj[curr][1]);
  	cr = visit(adj[curr][1]);
  	viss[curr] = 1;
  	viss[adj[curr][1]] = 1;
  }
  else if(c1 == 1 and c == 2 and c2 == 2){
  	cr = visit(adj[curr][1]);
  	Q.push(adj[curr][1]);
  	viss[curr] = 1;
  	viss[adj[curr][1]] = 1;
  }
  else if(c1 == 2 and c == 2 and c2 == 1){
  	cr = visit(adj[curr][0]);
  	Q.push(adj[curr][0]);
  	viss[curr] = 1;
  	viss[adj[curr][0]] = 1;
  }
  else if(c1 == 1 and c == 2 and c2 == 0){
  	cr = visit(adj[curr][1]);
  	Q.push(adj[curr][1]);
  	viss[curr] = 1;
  	viss[adj[curr][1]] = 1;
  }
  else if(c1 == 2 and c == 0 and c2 == 1){
  	cr = visit(adj[curr][1]);
  	Q.push(adj[curr][1]);
  	viss[curr] = 1;
  	viss[adj[curr][1]] = 1;
  }
  
  else if(c1 == 2 and c == 1 and c2 == 0){
  	cr = visit(adj[curr][0]);
  	Q.push(adj[curr][0]);
  	viss[curr] = 1;
  	viss[adj[curr][0]] = 1;
  }
  else if(c1 == 1 and c == 0 and c2 == 2){
  	cr = visit(adj[curr][0]);
  	Q.push(adj[curr][0]);
  	viss[curr] = 1;
  	viss[adj[curr][0]] = 1;
  }
  else if(adj[curr][0] == 0 and c == 2 and c2 == 1){
  	cr = visit(adj[curr][0]);
  	Q.push(adj[curr][0]);
  	viss[curr] = 1;
  	viss[adj[curr][0]] = 1;
  }
  // cout<<Q.front()<<" "<<c1<<" "<<c<<" "<<c2<<endl;
  int nt;
  while(Q.size()){
  	int x = Q.front();
  	Q.pop();
  	for(int i:adj[x]){
  		if(!viss[i]){
  			// cout<<x<<" "<<i<<endl;
  			viss[i] = 1;
  			nt = visit(i);
  			// cout<<pv<<" "<<cr<<" "<<nt<<endl;
  			if(nt == 2 and cr == 2 and pv == 2){
  				int res = visit(x);
  				
  				return;

  			}
  			Q.push(i);
  			pv = cr;
  			cr = nt;
  		}
  	}

  }
  return;
}

// int main(){
	// vector<pair<int,int>>qur = {{1,2},{2,3},{3,4},{4,5}};	
	// an = mark(qur,4);
	// for(auto i:an){
		// cout<<i<<" ";
	// }
	// cout<<endl;
	// locate(qur,2,0);
	// cout<<ans<<endl;
// }

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40