제출 #1065082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065082		beaconmc	The Ties That Guide Us (CEOI23_incursion)	C++17	30 / 100	278 ms	15772 KiB

incursion

#include "incursion.h"

#include <bits/stdc++.h>
 
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;



ll sub[50000];
vector<ll> edges[50000];
ll par[50000];
ll visited[50000];
ll depth[50000];
ll unsure[50000];
ll n;



void dfs(ll a, ll p, ll d){
    depth[a] = d;
    par[a] = p;
    sub[a] = 1;
    for (auto&i : edges[a]){
        if (i != p) dfs(i,a,d+1), sub[a] += sub[i];
    }
}

ll centfind(ll a, ll p){
    visited[a] = 1;
    for (auto&i : edges[a]){
        if (i!=p && sub[i] > n/2) return centfind(i, a);
    }
    return a;
}





vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
    n = (ll)F.size()+1;
    vector<int> ties(n);

    FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0, visited[i] = 0;

    for (auto&i : F){
        edges[i.first].push_back(i.second);
        edges[i.second].push_back(i.first);
    }
    dfs(3, -1, 0);

    ll cent = centfind(3, -1);
    ll root = -1;
    FOR(i,1,n+1){
        if (!visited[i]){
            root = i;
            dfs(root, -1, 0);
            break;
        }
    }
    ll cent2 = centfind(root, -1);


    dfs(cent, -1, 0);


    FOR(i,0,50000) visited[i] = 0;

    while (safe != -1){
        ties[safe-1] = 1;
        if (safe==cent || safe==cent2) break;
        safe = par[safe];
    }

    return ties;


}

bool cmp(ll a, ll b){
    return sub[a] < sub[b];
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
    n = (ll)F.size()+1;

    FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0, visited[i] = 0;

    for (auto&i : F){
        edges[i.first].push_back(i.second);
        edges[i.second].push_back(i.first);
    }
    dfs(1, -1, 0);

    ll cent = centfind(1, -1);
    ll root = -1;
    FOR(i,1,n+1){
        if (!visited[i]){
            root = i;
            dfs(root, -1, 0);
            break;
        }
    }
    ll cent2 = centfind(root, -1);


    dfs(cent, -1, 0);
    FOR(i,0,50000) visited[i] = 0;
    visited[curr] = 1;

    //cout << cent << endl;

    while (t != 1 && curr != cent){
        t = visit(par[curr]);
        curr = par[curr];
        visited[curr] = 1;
    }
    if (t != 1){
        t = visit(cent2);
        curr = cent2;
        visited[curr] = 1;
    }

    while (1){


        visited[curr] = 1;
        if (t==0 && curr!=cent){
            t = visit(par[curr]);
            curr = par[curr];
            continue;
        }
        sort(edges[curr].begin(), edges[curr].end(), cmp);
        reverse(edges[curr].begin(), edges[curr].end());
        bool done = false;


        for (auto&i : edges[curr]){

            if (i==par[curr]) continue;

            if (!visited[i]){
                visited[i] = true;
                t = visit(i);
                curr = i;
                done = true;
                break;
            }
        }

        if (!done){
            return;
        }


    }



}

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

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: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40