oj.uz

Submission #286646

# Submission time Handle Problem Language Result Execution time Memory
286646 2020-08-30T16:03:34 Z stoyan_malinin Toy Train (IOI17_train) C++14
16 / 100
 1172 ms 50744 KB 
#include "train.h"
//#include "grader.cpp"

#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 5005;

int n;
vector <int> adj[MAXN];
int owner[MAXN], charging[MAXN];

int guessSubtask(vector <int> a, vector <int> r, vector <int> u, vector <int> v)
{
    bool sub1 = true;
    for(int i = 0;i<u.size();i++)
    {
        if(u[i]!=v[i] && u[i]+1!=v[i])
        {
            sub1 = false;
            break;
        }
    }
    if(sub1==true) return 1;

    bool sub3 = true;
    for(int i = 0;i<a.size();i++)
    {
        if(a[i]!=1)
        {
            sub3 = false;
            break;
        }
    }
    if(sub3==true) return 3;

    bool sub4 = true;
    for(int i = 0;i<a.size();i++)
    {
        if(a[i]!=0)
        {
            sub4 = false;
            break;
        }
    }
    if(sub4==true) return 4;

    return -1;
}

vector <int> solve1()
{
    vector <int> res(n, -1);

    for(int s = 0;s<n;s++)
    {
        int x = s;
        while(true)
        {
            int goal = -1;
            if(owner[x]==1)
            {
                if(charging[x]==1) goal = x;
                else goal = x + 1;

                bool found = false;
                for(int y: adj[x])
                {
                    if(y==goal)
                    {
                        found =true;
                        break;
                    }
                }

                if(found==true)
                {
                    if(goal==x)
                    {
                        res[s] = true;
                        break;
                    }
                    else
                    {
                        x = x + 1;
                    }
                }
                else
                {
                    if(goal==x)
                    {
                        x = x + 1;
                    }
                    else
                    {
                        res[s] = false;
                        break;
                    }
                }
            }
            else
            {
                if(charging[x]==1) goal = x + 1;
                else goal = x;

                bool found = false;
                for(int y: adj[x])
                {
                    if(y==goal)
                    {
                        found =true;
                        break;
                    }
                }

                if(found==true)
                {
                    if(goal==x)
                    {
                        res[s] = false;
                        break;
                    }
                    else
                    {
                        x = x + 1;
                    }
                }
                else
                {
                    if(goal==x)
                    {
                        x = x + 1;
                    }
                    else
                    {
                        res[s] = true;
                        break;
                    }
                }
            }
        }
    }

    return res;
}

bool reachable[MAXN][MAXN][2];
void dfsMark(int x, int start, int depth, bool mode = false)
{
    if(depth!=0) reachable[start][x][mode] = true;
    for(int y: adj[x])
    {
        if(reachable[start][y][mode]==true) continue;
        if(mode==true && charging[y]==1) continue;

        dfsMark(y, start, depth+1, mode);
    }
}


vector <int> solve3()
{
    vector <int> res(n, -1);
    for(int i = 0;i<n;i++) dfsMark(i, i, 0, false);

    vector <int> chargingStations;
    for(int i = 0;i<n;i++)
    {
        if(charging[i]==1) chargingStations.push_back(i);
    }

    vector <bool> goodCycle(n, false);
    for(int x = 0;x<n;x++)
    {
        bool ans = false;
        for(int station: chargingStations)
        {
            if(reachable[x][station][0]==true && reachable[station][x][0]==true)
            {
                ans = true;
                break;
            }
        }
        if(charging[x]==true)
        {
            for(int i = 0;i<n;i++)
            {
                if(i==x) continue;
                if(reachable[x][i][0]==true && reachable[i][x][0]==true)
                {
                    ans = true;
                    break;
                }
            }
        }

        goodCycle[x] = ans;
        //cout << "goodCycle[" << x << "] = " << ans << '\n';
    }

    for(int s = 0;s<n;s++)
    {
        //cout << " ---- " << s << " --- " << '\n';

        res[s] = goodCycle[s];
        for(int x = 0;x<n;x++)
        {
            //cout << x << " -> " << reachable[s][x] << '\n';
            if(reachable[s][x][0]==true && goodCycle[x]==true)
            {
                res[s] = true;
                break;
            }
        }
    }

    return res;
}

vector <int> solve4()
{
    vector <int> res(n, -1);
    for(int i = 0;i<n;i++)
    {
        dfsMark(i, i, 0, false);
        if(charging[i]==0) dfsMark(i, i, 0, true);
    }

    vector <bool> goodCycle(n, false);
    for(int x = 0;x<n;x++)
    {
        if(charging[x]==true) continue;

        bool ans = false;
        for(int i = 0;i<n;i++)
        {
            if(reachable[x][i][0]==true && reachable[i][x][0]==true)
            {
                ans = true;
                break;
            }
        }

        goodCycle[x] = ans;
    }

    for(int s = 0;s<n;s++)
    {
        res[s] = goodCycle[s];
        for(int x = 0;x<n;x++)
        {
            //cout << x << " -> " << reachable[s][x] << '\n';
            if(reachable[s][x][0]==true && goodCycle[x]==true)
            {
                res[s] = true;
                break;
            }
        }
    }

    return res;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
    n = a.size();
    for(int i = 0;i<n;i++)
    {
        owner[i] = a[i];
        charging[i] = r[i];
    }

    for(int i = 0;i<u.size();i++)
    {
        adj[ u[i] ].push_back(v[i]);
    }

    for(int i = 0;i<n;i++)
    {
        sort(adj[i].begin(), adj[i].end());
        auto it = unique(adj[i].begin(), adj[i].end());
        adj[i].resize(it-adj[i].begin());
    }

    int subtask = guessSubtask(a, r, u, v);

    if(subtask==1) return solve1();
    else if(subtask==3) return solve3();
    else if(subtask==4) return solve4();

    return {};
}
/*
3 3
0 0 0
0 0 0
0 0
1 0
2 1
*/

Compilation message

train.cpp: In function 'int guessSubtask(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0;i<u.size();i++)
      |                   ~^~~~~~~~~
train.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0;i<a.size();i++)
      |                   ~^~~~~~~~~
train.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0;i<a.size();i++)
      |                   ~^~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:278:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |     for(int i = 0;i<u.size();i++)
      |                   ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 4 ms 896 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 4 ms 896 KB Output is correct
11 Correct 4 ms 896 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 50612 KB Output is correct
2 Correct 417 ms 50548 KB Output is correct
3 Correct 470 ms 50608 KB Output is correct
4 Correct 1132 ms 50500 KB Output is correct
5 Correct 874 ms 50508 KB Output is correct
6 Correct 711 ms 50228 KB Output is correct
7 Correct 504 ms 50160 KB Output is correct
8 Correct 371 ms 50232 KB Output is correct
9 Correct 384 ms 50240 KB Output is correct
10 Correct 418 ms 50236 KB Output is correct
11 Correct 369 ms 50116 KB Output is correct
12 Correct 94 ms 46028 KB Output is correct
13 Correct 1172 ms 50484 KB Output is correct
14 Correct 1135 ms 50616 KB Output is correct
15 Correct 1160 ms 50744 KB Output is correct
16 Correct 1139 ms 50460 KB Output is correct
17 Correct 1140 ms 50612 KB Output is correct
18 Correct 616 ms 50296 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 907 ms 50404 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1280 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 4 ms 896 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 4 ms 896 KB Output is correct
11 Correct 4 ms 896 KB Output is correct
12 Incorrect 1 ms 384 KB WA in grader: Wrong returned array size
13 Halted 0 ms 0 KB -