oj.uz

Submission #145959

# Submission time Handle Problem Language Result Execution time Memory
145959 2019-08-21T13:00:11 Z JovanK26 Split the Attractions (IOI19_split) C++14
7 / 100
 393 ms 20804 KB 
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector< vector<int> > v(200001);
vector< pair<vector<int>,int> >g(200001);
bool cmp(pair<vector<int>,int> i,pair<vector<int>,int> j)
{
   return i.first.size()<j.first.size();
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	vector<int> rez(n);
    for(int i=0;i<n;i++)
    {
        rez[i]=0;
    }
	for(int i=0;i<p.size();i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }
	if(a==1)
    {
        bool pr=0;
        if(b>c)
        {
            swap(b,c);
            pr=1;
        }
        for(int i=0;i<n;i++)
        {
            g[i]=make_pair(v[i],i);
        }
        sort(g.begin(),g.begin()+n,cmp);
        bool vis[n];
        queue<int> q;
        for(int i=0;i<n;i++)
        {
            rez[i]=0;
            vis[i]=0;
        }
        sort(g.begin(),g.begin()+n,cmp);
        int start=g[0].second;
        vis[start]=1;
        rez[start]=1;
        int br=0;
        int node=g[n-1].second;
        q.push(node);
        vis[node]=1;
        while(!q.empty())
        {
            int cur=q.front();
            q.pop();
           if(!pr)
           {
               rez[cur]=2;
           }
           else
           {
               rez[cur]=3;
           }
            br++;
            if(br==b)break;
            for(int i=0;i<v[node].size();i++)
            {
                if(!vis[v[node][i]])
                {
                    vis[v[node][i]]=1;
                    q.push(v[node][i]);
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(rez[i]==0)
            {
                if(!pr)
                {
                    rez[i]=3;
                }
                else
                {
                    rez[i]=2;
                }
            }
        }
    }
    else
    {

        int ind=-1;
        for(int i=0;i<n;i++)
        {
            if(v[i].size()==1)
            {
                ind=i;
                break;
            }
        }
        if(ind==-1)ind=0;
        int br=1;
        rez[ind]=1;
        int prev=ind;
        int cur=v[ind][0];
        while(br<a+b)
        {
            if(br<a)
            {
                rez[cur]=1;
            }
            else
            {
                rez[cur]=2;
            }
            br++;
            if(v[cur].size()==1)
            {
                prev=cur;
                cur=v[cur][0];
            }
            else
            {
                if(v[cur][0]==prev)
                {
                    prev=cur;
                    cur=v[cur][1];
                }
                else
                {
                    prev=cur;
                    cur=v[cur][0];
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(rez[i]==0)rez[i]=3;
        }
    }
    return rez;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++)
              ~^~~~~~~~~
split.cpp:64:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<v[node].size();i++)
                         ~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11256 KB ok, correct split
2 Correct 12 ms 11256 KB ok, correct split
3 Correct 11 ms 11256 KB ok, correct split
4 Correct 11 ms 11256 KB ok, correct split
5 Correct 12 ms 11256 KB ok, correct split
6 Correct 12 ms 11256 KB ok, correct split
7 Correct 123 ms 16372 KB ok, correct split
8 Correct 370 ms 19608 KB ok, correct split
9 Correct 84 ms 16404 KB ok, correct split
10 Correct 328 ms 19576 KB ok, correct split
11 Correct 90 ms 16428 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11300 KB ok, correct split
2 Correct 12 ms 11256 KB ok, correct split
3 Correct 12 ms 11256 KB ok, correct split
4 Correct 393 ms 20804 KB ok, correct split
5 Incorrect 352 ms 19704 KB invalid split: #1=1, #2=20, #3=99978
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11256 KB ok, correct split
2 Incorrect 77 ms 16504 KB invalid split: #1=1, #2=4, #3=99995
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11256 KB invalid split: #1=3, #2=2, #3=4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11256 KB ok, correct split
2 Correct 12 ms 11256 KB ok, correct split
3 Correct 11 ms 11256 KB ok, correct split
4 Correct 11 ms 11256 KB ok, correct split
5 Correct 12 ms 11256 KB ok, correct split
6 Correct 12 ms 11256 KB ok, correct split
7 Correct 123 ms 16372 KB ok, correct split
8 Correct 370 ms 19608 KB ok, correct split
9 Correct 84 ms 16404 KB ok, correct split
10 Correct 328 ms 19576 KB ok, correct split
11 Correct 90 ms 16428 KB ok, correct split
12 Correct 11 ms 11300 KB ok, correct split
13 Correct 12 ms 11256 KB ok, correct split
14 Correct 12 ms 11256 KB ok, correct split
15 Correct 393 ms 20804 KB ok, correct split
16 Incorrect 352 ms 19704 KB invalid split: #1=1, #2=20, #3=99978
17 Halted 0 ms 0 KB -