oj.uz

Submission #233167

# Submission time Handle Problem Language Result Execution time Memory
233167 2020-05-19T18:49:31 Z Andrei_Cotor Meetings (JOI19_meetings) C++14
0 / 100
 120 ms 2376 KB 
#include"meetings.h"
#include<random>
#include<algorithm>
#include<chrono>
#include<map>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> Subarb[36005];
vector<int> Path[36005];
int nrs;
map<int,int> IndSub[2005];
int rt;

bool cmp(int a, int b)
{
    if(a==rt)
        return 1;
    if(b==rt)
        return 0;
    int lca=Query(rt,a,b);
    return lca==a;
}

void getArb(int root, int subarb)
{
    shuffle(Subarb[subarb].begin(),Subarb[subarb].end(),rng);
    int nodeOnPath=Subarb[subarb][0];
    if(nodeOnPath==root)
        nodeOnPath=Subarb[subarb][1];

    Path[subarb].clear();
    for(auto node:Subarb[subarb])
    {
        if(node==nodeOnPath || node==root)
            continue;

        int lca=Query(root,node,nodeOnPath);
        if(lca==node)
        {
            Path[subarb].push_back(node);
        }
        else
        {
            if(IndSub[subarb][lca]==0)
            {
                IndSub[subarb][lca]=++nrs;
            }

            Subarb[IndSub[subarb][lca]].push_back(node);
        }
    }

    rt=root;
    Path[subarb].push_back(root);
    Path[subarb].push_back(nodeOnPath);
    sort(Path[subarb].begin(),Path[subarb].end(),cmp);

    for(int i=0; i<Path[subarb].size(); i++)
    {
        if(i<=Path[subarb].size()-2)
        {
            Bridge(Path[subarb][i],Path[subarb][i+1]);
        }

        if(IndSub[subarb][Path[subarb][i]]!=0)
        {
            Subarb[IndSub[subarb][Path[subarb][i]]].push_back(Path[subarb][i]);
            getArb(Path[subarb][i],IndSub[subarb][Path[subarb][i]]);
        }
    }
}

void Solve(int n) 
{
    for(int i=0; i<n; i++)
        Subarb[0].push_back(i);

    getArb(0,0);
}

Compilation message

meetings.cpp: In function 'void getArb(int, int)':
meetings.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<Path[subarb].size(); i++)
                  ~^~~~~~~~~~~~~~~~~~~~
meetings.cpp:62:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i<=Path[subarb].size()-2)
            ~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2176 KB Output is correct
2 Incorrect 5 ms 2176 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2176 KB Output is correct
2 Incorrect 5 ms 2176 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2176 KB Output is correct
2 Incorrect 5 ms 2176 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 2376 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -