Submission #1013095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013095		snpmrnhlol	Meetings (JOI19_meetings)	C++17	7 / 100	2 ms	1112 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3;
const int mod = 998244853;
const int inf = 2e9;
int rng = 123456;
int genrandom(){
    rng = (1ll*rng*101 + 29)%mod;
    return rng;
}
vector <int> e[N];
vector <int> nr;
int bad[N];
bool vis[N];
int sub[N];
void addedge(int x,int u,int w){
    vis[x] = 1;
    nr.push_back(x);
    //cout<<"addedge:"<<x<<' '<<u<<' '<<w<<'\n';
    if(w == -1){
        e[u].push_back(x);
        e[x].push_back(u);
        return;
    }else{
        for(int i = 0;i < e[u].size();i++){
            if(e[u][i] == w){
                swap(e[u][i],e[u].back());
                e[u].pop_back();
                break;
            }
        }
        swap(u,w);
        for(int i = 0;i < e[u].size();i++){
            if(e[u][i] == w){
                swap(e[u][i],e[u].back());
                e[u].pop_back();
                break;
            }
        }
        e[u].push_back(x);
        e[x].push_back(u);
        e[x].push_back(w);
        e[w].push_back(x);
    }
}
void cendecomp(int x, int node = nr[0]){
    int sz = 0;
    int cen = -1,cennr = inf;
    auto dfs = [&](auto self, int node, int p) -> void{
        sz++;
        sub[node] = 1;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
            sub[node]+=sub[i];
        }
    };
    auto dfs2 = [&](auto self, int node, int p) -> void{
        int mx = -1;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
            if(mx < sub[i]){
                mx = sub[i];
            }
        }
        if(mx < sz - sub[node]){
            mx = sz - sub[node];
        }
        if(cennr > mx){
            cennr = mx;
            cen = node;
        }
    };
    sz = 0;
    dfs(dfs, node, -1);
    dfs2(dfs2, node, -1);
    dfs(dfs, cen, -1);
    vector <int> cands;
    for(auto i:e[cen]){
        if(bad[i])continue;
        cands.push_back(i);
    }
    sort(cands.begin(),cands.end(),[&](int a, int b){
         return sub[a] > sub[b];
    });
    if(cands.empty()){
        ///fuck it i give up
        addedge(x,cen,-1);
        return;
    }/*cout<<"centroid:"<<cen<<'\n';
    for(int i = 0;i < (int)cands.size();i++){
        cout<<cands[i]<<' ';
    }
    cout<<'\n';*/
    bad[cen] = 1;
    for(int i = 0;i < (int)cands.size() - 1;i+=2){
        int p = Query(cands[i],cands[i + 1],x);
        if(p == cands[i] || p == cands[i + 1]){
            cendecomp(x, p);
            return;
        }else if(p == x){
            ///what the fuck
            int q = Query(cands[i],cen,x);
            if(q == x){
                addedge(x,cands[i],cen);
            }else if(q == cen){
                addedge(x,cands[i + 1],cen);
            }else{
                ///fcuk
                assert(0);
            }
            return;
        }else if(p != cen){
            assert(0);
            return;
        }
    }
    if(0 && cands.size()%2 == 0){
        addedge(x,cen,-1);
    }else{
        int p = Query(cands[(int)cands.size() - 1],cen,x);
        if(p == x){
            addedge(x,cands[(int)cands.size() - 1],cen);
        }else if(p == cands[(int)cands.size() - 1]){
            cendecomp(x, cands[(int)cands.size() - 1]);
        }else if(p == cen){
            addedge(x,cen,-1);
        }else{
            addedge(p, cands[(int)cands.size() - 1], cen);
        }
    }
}
void add(int x){
    if(nr.empty()){
        nr.push_back(x);
        vis[x] = 1;
        return;
    }else if(nr.size() == 1){
        addedge(x,nr[0],-1);
        return;
    }
    //cout<<"add:"<<x<<'\n';
    for(int i = 0;i < nr.size();i++){
        //cout<<nr[i]<<' ';
        bad[nr[i]] = 0;
    }
    //cout<<'\n';
    cendecomp(x);
}
void Solve(int n){
    while(nr.size() < n){
        int id = genrandom()%n;
        //cout<<genrandom()%n<<'\n';
        if(!vis[id]){
            add(id);
        }
    }
    for(int i = 0;i < n;i++){
        for(auto j:e[i]){
            if(i < j){
                //cout<<i<<' '<<j<<'\n';
                Bridge(i, j);
            }
        }
    }
}
/**
5
0 1
0 2
1 3
1 4
**/

Compilation message (stderr)

meetings.cpp: In function 'void addedge(int, int, int)':
meetings.cpp:26:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i = 0;i < e[u].size();i++){
      |                       ~~^~~~~~~~~~~~~
meetings.cpp:34:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i = 0;i < e[u].size();i++){
      |                       ~~^~~~~~~~~~~~~
meetings.cpp: In function 'void add(int)':
meetings.cpp:145:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i = 0;i < nr.size();i++){
      |                   ~~^~~~~~~~~~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:153:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  153 |     while(nr.size() < n){
      |           ~~~~~~~~~~^~~

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