Submission #369856

#	Time	Username	Problem	Language	Result	Execution time	Memory
369856		azberjibiou	Meetings (JOI19_meetings)	C++17	0 / 100	3065 ms	620 KiB

meetings

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

Compilation message (stderr)

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int j=0;j<g[cent].size();j++)
      |                         ~^~~~~~~~~~~~~~~
meetings.cpp:76:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                         for(int k=0;k<v[cent].size();k++)   if(v[cent][k]==nxt)  v[cent][k]=i;
      |                                     ~^~~~~~~~~~~~~~~
meetings.cpp:77:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                         for(int k=0;k<v[nxt].size();k++)    if(v[nxt][k]==cent) v[nxt][k]=i;
      |                                     ~^~~~~~~~~~~~~~
meetings.cpp:92:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                         for(int k=0;k<v[cent].size();k++)   if(v[cent][k]==nxt) v[cent][k]=res;
      |                                     ~^~~~~~~~~~~~~~~
meetings.cpp:93:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                         for(int k=0;k<v[nxt].size();k++)    if(v[nxt][k]==cent) v[nxt][k]=res;
      |                                     ~^~~~~~~~~~~~~~

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