제출 #1081398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081398		thelegendary08	The Ties That Guide Us (CEOI23_incursion)	C++17	42 / 100	279 ms	10796 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;
const int mxn = 45005;
bool vis[mxn];
int sts[mxn];
vector<int>adj[mxn];
int dfs(int x, int p){
    vis[x] = 1;
    int cur = 1;
    for(auto u : adj[x]){
        if(u != p){
            cur += dfs(u, x);
        }
    }
    return cur;
}
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;

	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{
        int thing = dfs(two, -1);
	    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;
        vi d(n+1, 0);

        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;
                    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 : adj[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 : adj[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;
        }

	}



}

컴파일 시 표준 에러 (stderr) 메시지

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:68:13: warning: unused variable 'thing' [-Wunused-variable]
   68 |         int thing = dfs(two, -1);
      |             ^~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:129:13: warning: unused variable 'col' [-Wunused-variable]
  129 |         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: 30 / 30
• Subtask 3: 0 / 40