제출 #1271576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271576		Andrey	Meetings (JOI19_meetings)	C++20	0 / 100	219 ms	760 KiB

meetings

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

vector<int> haha[2001];
vector<bool> bruh(2001);
vector<bool> yo(2001,true);
vector<int> st(2001);
vector<int> par(2001);
vector<int> wut(0);

void edge(int x, int y) {
    haha[x].push_back(y);
    haha[y].push_back(x);
}

void rem(int x, int y) {
    bool yeah = false;
    for(int i = 0; i < haha[x].size(); i++) {
        if(yeah) {
            swap(haha[x][i],haha[x][i-1]);
        }
        if(haha[x][i] == y) {
            yeah = true;
        }
    }
    haha[x].pop_back();
    yeah = false;
    for(int i = 0; i < haha[y].size(); i++) {
        if(yeah) {
            swap(haha[y][i],haha[y][i-1]);
        }
        if(haha[y][i] == x) {
            yeah = true;
        }
    }
    haha[y].pop_back();
}

void dfs(int a, int t) {
    st[a] = 1;
    par[a] = t;
    wut.push_back(a);
    for(int v: haha[a]) {
        if(v != t && bruh[v]) {
            dfs(v,a);
            st[a]+=st[v];
        }
    }
}

void dude(int a, int z) {
    wut.clear();
    dfs(a,-1);
    if(st[a] == 1) {
        haha[a].push_back(z);
        haha[z].push_back(a);
        return;
    }
    if(st[a] == 2) {
        int y = Query(wut[0],wut[1],z);
        if(y == wut[0]) {
            edge(z,wut[0]);
        }
        else if(y == wut[1]) {
            edge(z,wut[1]);
        }
        else {
            rem(wut[0],wut[1]);
            edge(y,wut[0]);
            edge(y,wut[1]);
            if(y != z) {
                yo[y] = false;
                edge(y,z);
            }
        }
        return;
    }
    int c = a;
    bool yeah = true;
    while(yeah) {
        yeah = false;
        for(int v: haha[c]) {
            if(bruh[v] && st[v] < st[c] & st[v]*2 >= st[a]) {
                c = v;
                yeah = true;
            }
        }
    }
    vector<pair<int,int>> banana(0);
    for(int v: haha[c]) {
        if(bruh[v]) {
            if(st[v] < st[c]) {
                banana.push_back({st[v],v});
            }
            else {
                banana.push_back({st[a]-st[c],v});
            }
        }
    }
    sort(banana.begin(),banana.end());
    reverse(banana.begin(),banana.end());
    int x = banana[0].second,y = banana[1].second;
    int w = Query(x,y,z);
    if(w == x || w == y) {
        bruh[c] = false;
        dude(w,z);
    }
    else if(w == c) {
        bruh[x] = false;
        bruh[y] = false;
        dude(c,z);
    }
    else {
        if(Query(w,c,x) == w) {
            rem(c,x);
            edge(w,c);
            edge(w,x);
            if(z != w) {
                edge(z,w);
                yo[w] = false;
            }
        }
        else {
            rem(c,y);
            edge(w,c);
            edge(w,y);
            if(z != w) {
                edge(z,w);
                yo[w] = false;
            }
        }
    }
}

vector<pair<int,int>> ans(0);

void troll(int a, int t) {
    for(int v: haha[a]) {
        if(v != t) {
            Bridge(a,v);
            troll(v,a);
        }
    }
}

void Solve (int n) {
    vector<int> wow(0);
    for(int i = 0; i < n; i++) {
        wow.push_back(i);
    }
    random_shuffle(wow.begin(),wow.end());
    haha[wow[0]].push_back(wow[1]);
    haha[wow[1]].push_back(wow[0]);
    for(int i = 2; i < n; i++) {
        if(yo[wow[i]]) {
            for(int j = 0; j < n; j++) {
                bruh[j] = 1;
            }
            dude(wow[0],wow[i]);
        }
    }
    troll(wow[0],-1);
}

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

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:153:19: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
  153 |     random_shuffle(wow.begin(),wow.end());
      |     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from meetings.cpp:3:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71