Submission #1081421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081421		thelegendary08	The Ties That Guide Us (CEOI23_incursion)	C++17	100 / 100	293 ms	14528 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"
#define f0r(i,n) for(int i = 0;i<n;i++)
#define vi vector<int>
#define pb push_back
using namespace std;
const int mxn = 45005;
int n;
int sts[mxn];
vector<int>adj[mxn];
int dfs(int x, int p){
    int cur = 1;
    for(auto u : adj[x]){
        if(u != p){
            cur += dfs(u, x);
        }
    }
    sts[x] = cur;
    return cur;
}
int centroid(int x, int p){
    for(auto u : adj[x]){
        if(u != p && sts[u] > n/2)return centroid(u, x);
    }
    return x;
}

int sts2[mxn];
vector<int>adj2[mxn];

int dfs2(int x, int p){
    int cur = 1;
    for(auto u : adj2[x]){
        if(u != p){
            cur += dfs2(u, x);
        }
    }
    sts2[x] = cur;
    return cur;
}
int centroid2(int x, int p){
    for(auto u : adj2[x]){
        if(u != p && sts2[u] > n/2)return centroid2(u, x);
    }
    return x;
}

int stsc[mxn];
int dfs3(int x, int p){
    int cur = 1;
    for(auto u : adj2[x]){
        if(u != p){
            cur += dfs3(u, x);
        }
    }
    stsc[x] = cur;
    return cur;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {

    safe--;

	int two;
	n = F.size() + 1;
	vector<int>dist(n);
	dist[safe] = 0;

	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';
    dfs(0, -1);
    //f0r(i,n)cout<<sts[i]<<' ';
    //cout<<'\n';
    int centroid1 = centroid(0, -1);
    vi centroids = {centroid1};
    for(auto u : adj[centroid1]){
        dfs(u, -1);
        int thing = centroid(u, -1);
        //cout<<u<<' '<<thing<<'\n';
        if(thing != centroid1){
            centroids.pb(thing);
            break;
        }
    }
    //for(auto u : centroids)cout<<u<<' ';
    //cout<<'\n';

    if(centroids.size() == 1){
        two = centroids[0];
        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;
    }
    else{
        vi col(n,0);
        vi par(n);
        par[centroids[0]] = centroids[1];
        par[centroids[1]] = centroids[0];
        queue<int>q;
        q.push(centroids[0]);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj[cur]){
                if(u != par[cur]){
                    par[u] = cur;
                    q.push(u);
                }
            }
        }
        q.push(centroids[1]);
        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;
        int cnt = 0;
        while(cnt == 0){

            //cout<<now<<'\n';
            col[now] = 1;
            if(now == centroids[0] || now == centroids[1])cnt++;
            now = par[now];
        }

        return col;
    }

    return {};
    /*
	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};
	n = F.size() + 1;
	vi deg(n+1);
	vi degcnt(4, 0);
	f0r(i, n-1){
		adj2[F[i].first].push_back(F[i].second);
		adj2[F[i].second].push_back(F[i].first);
		deg[F[i].first]++;
		deg[F[i].second]++;
	}
	dfs2(1, -1);
    //for(int i = 1; i<=n;i++)cout<<sts2[i]<<' ';
    //cout<<'\n';
    int centroid1 = centroid2(1, -1);
    vi centroids = {centroid1};
    for(auto u : adj2[centroid1]){
        dfs2(u, -1);
        int thing = centroid2(u, -1);
        if(thing != centroid1){
            centroids.pb(thing);
            break;
        }
    }
    //for(auto u : centroids)cout<<u<<' ';
    //cout<<'\n';
    int two;
    /*

	for(int i = 1; i<=n; i++){
        if(deg[i]==2)two = i;
        degcnt[deg[i]]++;
	}
	*/
	if(centroids.size() == 2){
        vi par(n+1);
        dfs3(centroids[0], centroids[1]);
        dfs3(centroids[1], centroids[0]);
        par[centroids[0]] = centroids[1];
        par[centroids[1]] = centroids[0];
        queue<int>q;
        q.push(centroids[0]);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj2[cur]){
                if(u != par[cur]){
                    par[u] = cur;
                    q.push(u);
                }
            }
        }
        q.push(centroids[1]);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj2[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 : adj2[cur]){
                if(!vis[u] && u != par[cur])thing.push_back({stsc[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;
        }
	}
	else{
        two = centroids[0];
        //cout<<two<<'\n';
        vi par(n+1);
        par[two] = -1;
        vi d(n+1, 0);

        queue<int>q;
        q.push(two);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj2[cur]){
                if(u != par[cur]){
                    par[u] = cur;
                    d[u] = d[cur] + 1;
                    q.push(u);
                }
            }
        }
        //for(int i = 1; i<=n; i++)cout<<d[i]<<' ';
        //cout<<'\n';
        vector<bool>viss(n+1, 0);
        vi sts(n+1, 0);


        priority_queue<pair<int,int>>pq;
        for(int i=1; i<=n;i++){
            if(deg[i] == 1){
                pq.push({d[i], i});
                sts[i] = 1;
                viss[i] = 1;
            }
        }
        while(!pq.empty()){
            int cur = pq.top().second;
            pq.pop();
            //cout<<cur<<'\n';
            //if(par[cur] != -1)sts[par[cur]] += sts[cur];
            if(par[cur] != -1 && !viss[par[cur]]){
                viss[par[cur]] = 1;
                for(auto u : adj2[par[cur]]){
                    if(u != par[par[cur]]){
                        sts[par[cur]] += sts[u];
                    }
                }
                pq.push({d[par[cur]], par[cur]});
            }
        }
        //for(int i = 1; i<=n; i++)cout<<sts[i]<<' ';
        //cout<<'\n';
        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 : adj2[cur]){
                if(!vis[u] && u != par[cur])thing.push_back({sts[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:237:6: warning: unused variable 'x' [-Wunused-variable]
  237 |  int x;
      |      ^
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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40