Submission #978724

#	Time	Username	Problem	Language	Result	Execution time	Memory
978724		happy_node	Meetings (JOI19_meetings)	C++17	29 / 100	1254 ms	6952 KiB

meetings

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

const int MX=2005;

set<pair<int,int>> edges;

bool used[MX], vis[MX];
int sz[MX];
int N;

vector<int> adj[MX];

int getSize(int v, int p) {
        sz[v]=1;
        for(auto u:adj[v]) {
                if(u!=p && !used[u]) {
                        sz[v]+=getSize(u,v);
                }
        }
        return sz[v];
}

int getCen(int v, int p, int s) {
        for(auto u:adj[v]) {
                if(u!=p && 2*sz[u]>s && !used[u]) {
                        return getCen(u,v,s);
                }
        }
        return v;
}

map<array<int,3>,int> memo;

int que(int u, int v, int w) {
        // cout<<"ask "<<u<<" "<<v<<" "<<w<<endl;
        array<int,3> arr={u,v,w};
        sort(arr.begin(),arr.end());
        if(memo.count(arr)) return memo[arr];
        // we can memo here
        return memo[arr]=Query(u,v,w);
}

void cdc(int v, int x) {
        // cout<<"at node : "<<v<<endl;

        int s=getSize(v,v);
        // cout<<"size : "<<s<<endl;
        int cen=getCen(v,v,s);
        getSize(cen,cen);
        used[cen]=true;

        // cout<<"at cen : "<<cen<<endl;

        bool fnd=0;

        vector<int> conds;
        for(auto u:adj[cen]) {
                if(used[u]) continue;
                conds.push_back(u);
        }

        if(conds.size()&1) conds.push_back(cen);
        assert(conds.size()<=20);

        for(int i=0;i<conds.size();i+=2) {
                int u=conds[i],v=conds[i+1];
                if(que(u,v,x)!=cen) {
                        if(que(u,cen,x)!=cen) {
                                int k=que(u,cen,x);
                                if(k==cen) {
                                        assert(false);
                                } else if(k==u) {
                                        if(sz[u]>1) cdc(u,x);
                                        else {
                                                vis[x]=true;
                                                edges.insert({min(u,x),max(u,x)});
                                        }
                                } else if(k==x) {
                                        vis[x]=true;
                                        edges.erase({min(u,cen),max(u,cen)});
                                        edges.insert({min(cen,x),max(cen,x)});
                                        edges.insert({min(u,x),max(u,x)});
                                } else {
                                        vis[x]=true;
                                        vis[k]=true;
                                        edges.erase({min(u,cen),max(u,cen)});
                                        edges.insert({min(cen,k),max(cen,k)});
                                        edges.insert({min(u,k),max(u,k)});
                                        edges.insert({min(x,k),max(x,k)});
                                }
                        } else {
                                int k=que(v,cen,x);
                                if(k==cen) {
                                        assert(false);
                                } else if(k==v) {
                                        if(sz[v]>1) cdc(v,x);
                                        else {
                                                vis[x]=true;
                                                edges.insert({min(v,x),max(v,x)});
                                        }
                                } else if(k==x) {
                                        vis[x]=true;
                                        edges.erase({min(v,cen),max(v,cen)});
                                        edges.insert({min(cen,x),max(cen,x)});
                                        edges.insert({min(v,x),max(v,x)});
                                } else {
                                        vis[x]=true;
                                        vis[k]=true;
                                        edges.erase({min(v,cen),max(v,cen)});
                                        edges.insert({min(cen,k),max(cen,k)});
                                        edges.insert({min(v,k),max(v,k)});
                                        edges.insert({min(x,k),max(x,k)});
                                }
                        }

                        fnd=1;
                        break;
                }
        }

        if(!fnd) {
                vis[x]=true;
                edges.insert({min(cen,x),max(cen,x)});
        }
}

void prep() {
        for(int i=0;i<N;i++) {
                used[i]=false;
                adj[i].clear();
        }
        for(auto [u,v]:edges) {
                adj[u].push_back(v);
                adj[v].push_back(u);
        }
}

void Solve(int _N) {
        N=_N;
                        
        vis[0]=true;

        for(int i=1;i<N;i++) {
                if(vis[i]) continue;
                // cout<<"try : "<<i<<endl;
                // for(auto [u,v]:edges) {
                //         cout<<u<<" "<<v<<endl;
                // } 
                prep();
                cdc(0,i);
        }
        
        for(auto [u,v]:edges) {
                if(u>v) swap(u,v);
                Bridge(u,v);
        }
}

Compilation message (stderr)

meetings.cpp: In function 'void cdc(int, int)':
meetings.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=0;i<conds.size();i+=2) {
      |                     ~^~~~~~~~~~~~~

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