Submission #1198639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198639		Hanksburger	Meetings (JOI19_meetings)	C++20	100 / 100	861 ms	1056 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[2005], tmp[2005], tmp2[2005], vec, vec2, path;
int dp[2005], done[2005];
void createEdge(int u, int v)
{
    //cout << "createEdge " << u << ' ' << v << '\n';
    adj[u].push_back(v);
    adj[v].push_back(u);
}
void deleteEdge(int u, int v)
{
    //cout << "deleteEdge " << u << ' ' << v << '\n';
    adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
    adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
}
void dfs(int u, int p)
{
    dp[u]=tmp[u].size();
    for (int v:tmp[u])
    {
        if (v==p)
            continue;
        dfs(v, u);
        dp[u]=max(dp[u], dp[v]);
    }
}
void dfs2(int u, int p)
{
    path.push_back(u);
    int node=-1;
    for (int v:tmp[u])
    {
        if (v==p)
            continue;
        if (node==-1 || dp[node]<dp[v])
            node=v;
    }
    if (node!=-1)
        dfs2(node, u);
}
void dfs3(int u, int p1, int p2)
{
    vec2.push_back(u);
    for (int v:tmp[u])
    {
        if (v==p1 || v==p2)
            continue;
        tmp2[u].push_back(v);
        tmp2[v].push_back(u);
        dfs3(v, u, u);
    }
}
void Solve(int n)
{
    createEdge(0, 1);
    done[0]=done[1]=1;
    for (int i=2; i<n; i++)
    {
        if (done[i])
            continue;
        vec.clear();
        for (int j=0; j<n; j++)
        {
            if (done[j])
            {
                vec.push_back(j);
                tmp[j].clear();
                for (int u:adj[j])
                    tmp[j].push_back(u);
            }
        }
        done[i]=1;
        while (1)
        {
            if (vec.size()==1)
            {
                createEdge(vec[0], i);
                break;
            }
            int root=-1;
            for (int u:vec)
                if (root==-1 || tmp[root].size()<tmp[u].size())
                    root=u;
            dfs(root, -1);
            int node1=-1, node2=-1;
            for (int u:tmp[root])
            {
                if (node1==-1 || dp[node1]<dp[u])
                {
                    node2=node1;
                    node1=u;
                }
                else if (node2==-1 || dp[node2]<dp[u])
                    node2=u;
            }
            path.clear();
            path.push_back(root);
            dfs2(node1, root);
            if (node2!=-1)
            {
                reverse(path.begin(), path.end());
                dfs2(node2, root);
            }
            int res=Query(path.front(), path.back(), i);
            if (res==i)
            {
                int l=0, r=path.size()-1;
                while (l+2<=r)
                {
                    int mid=(l+r)/2;
                    res=Query(path[l], path[mid], i);
                    if (res==i)
                        r=mid;
                    else
                        l=mid;
                }
                deleteEdge(path[l], path[r]);
                createEdge(path[l], i);
                createEdge(path[r], i);
                break;
            }
            int ind=-1;
            for (int j=0; j<path.size(); j++)
            {
                if (path[j]==res)
                {
                    ind=j;
                    break;
                }
            }
            if (ind==-1)
            {
                int l=0, r=path.size()-1;
                while (l+2<=r)
                {
                    int mid=(l+r)/2, newres=Query(path[l], path[mid], i);
                    if (newres==res)
                        r=mid;
                    else
                        l=mid;
                }
                deleteEdge(path[l], path[r]);
                createEdge(path[l], res);
                createEdge(path[r], res);
                createEdge(i, res);
                done[res]=1;
                break;
            }
            vec2.clear();
            for (int u:vec)
                tmp2[u].clear();
            dfs3(path[ind], ind?path[ind-1]:-1, ind+2<=path.size()?path[ind+1]:-1);
            vec=vec2;
            for (int u:vec)
            {
                tmp[u].clear();
                for (int v:tmp2[u])
                    tmp[u].push_back(v);
            }
        }
    }
    for (int i=0; i<n; i++)
        for (int u:adj[i])
            if (u>i)
                Bridge(i, u);
}

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