제출 #1284296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284296		muhammad-mutahir	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	55 ms	3820 KiB

incursion

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

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;
  int c = 2;
  while(Q.size()){
  	int x = Q.front();
  	Q.pop();
  	for(int i:adj[x]){
  		if(!vis[i-1]){
  			Q.push(i);
  			vis[i-1] = c;
  		}
  	}
  	c--;
  	c+=3;
  	c%=3;
  }
  // print(vis);
    
  return vis;
}


// int visit(int 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);
  int cr;
  if(c1 == 0 and c == 1 and c2 == 2){
  	Q.push(c2);
  	cr = visit(c2);
  	viss[c] = 1;
  	viss[c2] = 1;
  }
  else if(c1 == 1 and c == 2 and c2 == 0){
  	cr = visit(c2);
  	Q.push(c2);
  	viss[c] = 1;
  	viss[c2] = 1;
  }
  else if(c1 == 2 and c == 0 and c2 == 1){
  	cr = visit(c2);
  	Q.push(c2);
  	viss[c] = 1;
  	viss[c2] = 1;
  }
  
  else if(c1 == 2 and c == 1 and c2 == 0){
  	cr = visit(c1);
  	Q.push(c1);
  	viss[c] = 1;
  	viss[c1] = 1;
  }
  else if(c1 == 1 and c == 0 and c2 == 2){
  	cr = visit(c1);
  	Q.push(c1);
  	viss[c] = 1;
  	viss[c1] = 1;
  }
  else if(c1 == 0 and c == 2 and c2 == 1){
  	cr = visit(c1);
  	Q.push(c1);
  	viss[c] = 1;
  	viss[c1] = 1;
  }
  int nt;
  while(Q.size()){
  	int x = Q.front();
  	Q.pop();
  	for(int i:adj[x]){
  		if(!viss[i]){

  			viss[i] = 1;
  			nt = visit(i);
  			if(nt == 2 and cr == 2 and pv == 2){
  				int res = visit(x);
  				// return;
  				break;
  			}
  			Q.push(i);
  			pv = cr;
  			cr = nt;
  		}
  	}

  }
  return;
}

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

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