oj.uz

Submission #145923

# Submission time Handle Problem Language Result Execution time Memory
145923 2019-08-21T11:26:38 Z JovanK26 Split the Attractions (IOI19_split) C++14
7 / 100
 99 ms 19192 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)
    {
        if(b>c)swap(b,c);
        for(int i=0;i<n;i++)
        {
            g[i]=make_pair(v[i],i);
        }
        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();
            rez[cur]=2;
            br++;
            if(br==b-1)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)rez[i]=3;
        }
    }
    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++)
              ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11256 KB ok, correct split
2 Correct 11 ms 11256 KB ok, correct split
3 Correct 12 ms 11256 KB ok, correct split
4 Correct 12 ms 11256 KB ok, correct split
5 Correct 11 ms 11256 KB ok, correct split
6 Correct 12 ms 11256 KB ok, correct split
7 Correct 84 ms 17528 KB ok, correct split
8 Correct 87 ms 17528 KB ok, correct split
9 Correct 90 ms 17608 KB ok, correct split
10 Correct 78 ms 17500 KB ok, correct split
11 Correct 83 ms 17480 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11256 KB ok, correct split
2 Correct 11 ms 11256 KB ok, correct split
3 Correct 12 ms 11256 KB ok, correct split
4 Correct 99 ms 19192 KB ok, correct split
5 Incorrect 75 ms 17656 KB invalid split: #1=1, #2=6, #3=99992
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11256 KB ok, correct split
2 Incorrect 76 ms 16464 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 11 ms 11260 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 11 ms 11256 KB ok, correct split
2 Correct 11 ms 11256 KB ok, correct split
3 Correct 12 ms 11256 KB ok, correct split
4 Correct 12 ms 11256 KB ok, correct split
5 Correct 11 ms 11256 KB ok, correct split
6 Correct 12 ms 11256 KB ok, correct split
7 Correct 84 ms 17528 KB ok, correct split
8 Correct 87 ms 17528 KB ok, correct split
9 Correct 90 ms 17608 KB ok, correct split
10 Correct 78 ms 17500 KB ok, correct split
11 Correct 83 ms 17480 KB ok, correct split
12 Correct 11 ms 11256 KB ok, correct split
13 Correct 11 ms 11256 KB ok, correct split
14 Correct 12 ms 11256 KB ok, correct split
15 Correct 99 ms 19192 KB ok, correct split
16 Incorrect 75 ms 17656 KB invalid split: #1=1, #2=6, #3=99992
17 Halted 0 ms 0 KB -