Submission #1081383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081383		thelegendary08	The Ties That Guide Us (CEOI23_incursion)	C++17	12 / 100	284 ms	8288 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"
#define f0r(i,n) for(int i = 0;i<n;i++)
#define vi vector<int>
using namespace std;
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {

    safe--;
	int n;

	int two;
	n = F.size() + 1;
	vector<int>dist(n);
	dist[safe] = 0;
	vector<int>adj[n];
	vi deg(n, 0);
	vi degcnt(4, 0);
	f0r(i, n-1){
		adj[--F[i].first].push_back(--F[i].second);
		adj[F[i].second].push_back(F[i].first);
		deg[F[i].first]++;
		deg[F[i].second]++;
	}
	//f0r(i,n)cout<<deg[i]<<' ';
	//cout<<'\n';

	f0r(i,n){
	    if(deg[i] == 2)two = i;
        degcnt[deg[i]]++;
	}

	if(degcnt[3] == 0){
        vi col(n, 0);
        queue<int>q;
        q.push(safe);
        vector<bool>vis(n,0);
        vis[safe] = 1;

        col[safe] = 0;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj[cur]){
                if(vis[u])continue;
                vis[u] = 1;
                dist[u] = dist[cur] + 1;
                col[u] = (col[cur] + 1) % 3;
                q.push(u);
            }
        }
        return col;
	}
	else{
	    vi col(n,0);
        vi par(n);
        par[two] = -1;
        queue<int>q;
        q.push(two);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj[cur]){
                if(u != par[cur]){
                    par[u] = cur;
                    q.push(u);
                }
            }
        }
        //f0r(i,n)cout<<par[i]<<' ';
        //cout<<'\n';

        int now = safe;
        while(now != -1){
            //cout<<now<<'\n';
            col[now] = 1;
            now = par[now];
        }
        //cout<<cur<<'\n';
        //cout<<par[cur]<<'\n';

        //cout<<par[par[par[cur]]]<<'\n';
        return col;


	}


}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	int x;
	vector<int>nxt = {2, 0, 1};
	int n = F.size() + 1;
	vector<bool>vis(n+1, 0);
	vector<int>adj[n+1];
	vi deg(n+1);
	vi degcnt(4, 0);
	f0r(i, n-1){
		adj[F[i].first].push_back(F[i].second);
		adj[F[i].second].push_back(F[i].first);
		deg[F[i].first]++;
		deg[F[i].second]++;
	}
	int two;
	for(int i = 1; i<=n; i++){
        if(deg[i]==2)two = i;
        degcnt[deg[i]]++;
	}
	if(degcnt[3] == 0){
        vis[curr] = 1;
        //queue<int>q;
        //q.push(curr);
        bool found = false;
        int col = t;
        int cur = curr;
        vi cols(n+1, -1);
        cols[curr] = t;
        while(!found){
            bool ok = 0;
            for(auto u : adj[cur]){
                if(vis[u])continue;
                vis[u] = 1;
                x = visit(u);
                cols[u] = x;
                if(x == nxt[cols[cur]]){
                    cur = u;
                    ok = 1;
                    break;
                }
                else{
                    visit(cur);
                }
            }
            if(!ok)return;
        }
	}
	else{
        vi par(n+1);
        par[two] = -1;
        queue<int>q;
        q.push(two);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj[cur]){
                if(u != par[cur]){
                    par[u] = cur;
                    q.push(u);
                }
            }
        }
        vi vis(n+1, 0);
        int cur = curr;
        int col = t;
        int x;
        vis[cur] = 1;
        while(col == 0){
            cur = par[cur];
            vis[cur] = 1;
            x = visit(cur);
            col = x;
        }
        bool found = 0;
        while(!found){
            vector<pair<int,int>>thing;
            for(auto u : adj[cur]){
                if(!vis[u] && u != par[cur])thing.push_back({deg[u], u});
            }
            sort(thing.rbegin(), thing.rend());
            bool ok =0;
            for(auto u : thing){
                x = visit(u.second);
                if(x == 0){
                    visit(cur);
                }
                else{
                    cur = u.second;
                    vis[cur] = 1;
                    col = x;
                    ok = 1;
                    break;
                }
            }
            if(!ok)return;
        }

	}



}

Compilation message (stderr)

incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:114:13: warning: unused variable 'col' [-Wunused-variable]
  114 |         int col = t;
      |             ^~~
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

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