Submission #369889

#	Time	Username	Problem	Language	Result	Execution time	Memory
369889		azberjibiou	Meetings (JOI19_meetings)	C++17	29 / 100	2494 ms	17192 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define fir first
#define sec second
const int mxN=2020;
vector <int> v[mxN], g[mxN];
int msub[mxN];
bool Chk[mxN];
bool used[mxN];
int sub[mxN];
int par[mxN][mxN];
int findpar(int a, int b)
{
    if(par[a][b]==b)    return b;
    return par[a][b]=findpar(a, par[a][b]);
}
bool cmp1(int a, int b)
{
    return sub[a]>sub[b];
}
void dfs1(int now, int pre)
{
    //printf("now=%d\n", now);
    g[now].clear();
    sub[now]=1;
    msub[now]=-1;
    for(int pnxt : v[now])
    {
        int nxt=findpar(now, pnxt);
        if(Chk[nxt] || nxt==pre)    continue;
        dfs1(nxt, now);
        sub[now]+=sub[nxt];
        if(msub[now]==-1)   msub[now]=nxt;
        else if(sub[msub[now]]<sub[nxt])    msub[now]=nxt;
    }
}
void dfs2(int now, int pre)
{
    //printf("2now=%d\n", now);
    g[now].clear();
    sub[now]=1;
    for(int pnxt : v[now])
    {
        int nxt=findpar(now, pnxt);
        if(Chk[nxt] || nxt==pre)    continue;
        dfs2(nxt, now);
        sub[now]+=sub[nxt];
        g[now].push_back(nxt);
    }
}
void Solve(int N) {
    v[0].push_back(1);
    v[1].push_back(0);
    for(int i=0;i<N;i++)    for(int j=0;j<N;j++)    par[i][j]=j;
    for(int i=2;i<N;i++)
    {
        if(used[i]) continue;
        int root=i-1;
        for(int j=0;j<N;j++)    Chk[j]=false;
        int cnt=0;
        while(true)
        {
            dfs1(root, -1);
            int cent=root;
            while(!g[cent].empty() && sub[msub[cent]]*2>sub[cent])   cent=g[cent][0];
            dfs2(cent, -1);
            //printf("cent=%d\n", cent);
            //for(int j=0;j<i;j++)    printf("Chk[%d]=%d\n", j, Chk[j]);
            /*for(int j=0;j<i;j++)
            {
                printf("%d: ", j);
                for(int nxt : g[j]) printf("%d ", nxt);
                printf("\n");
            }*/
            if(g[cent].empty())
            {
                v[cent].push_back(i);
                v[i].push_back(cent);
                break;
            }
            bool ispar=true;
            bool flag=false;
            sort(g[cent].begin(), g[cent].end(), cmp1);
            for(int j=0;j<g[cent].size();j++)
            {
                int nxt=g[cent][j];
                int res=Query(cent, nxt, i);
                if(res!=cent)
                {
                    ispar=false;
                    if(res==i)
                    {
                        //printf("s1");
                        par[cent][nxt]=i;
                        par[nxt][cent]=i;
                        v[i].push_back(cent);
                        v[i].push_back(nxt);
                        flag=true;
                    }
                    else if(res==nxt)
                    {
                        //printf("s2");
                        root=nxt;
                        Chk[cent]=true;
                        //assert(cent!=nxt);
                    }
                    else
                    {
                        //printf("s3");
                        par[cent][nxt]=res;
                        par[nxt][cent]=res;
                        v[res].push_back(cent);
                        v[res].push_back(nxt);
                        v[i].push_back(res);
                        v[res].push_back(i);
                        used[res]=true;
                        flag=true;
                    }
                    break;
                }
            }
            if(flag)    break;
            if(ispar)
            {
                v[cent].push_back(i);
                v[i].push_back(cent);
                break;
            }
        }
    }
    for(int i=0;i<N;i++)
    {
        for(int pnxt : v[i])
        {
            int nxt=findpar(i, pnxt);
            if(nxt>i)   Bridge(i, nxt);
        }
    }
}

Compilation message (stderr)

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for(int j=0;j<g[cent].size();j++)
      |                         ~^~~~~~~~~~~~~~~
meetings.cpp:64:13: warning: unused variable 'cnt' [-Wunused-variable]
   64 |         int cnt=0;
      |             ^~~

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