oj.uz

Submission #286647

# Submission time Handle Problem Language Result Execution time Memory
286647 2020-08-30T16:09:50 Z stoyan_malinin Toy Train (IOI17_train) C++14
27 / 100
 1218 ms 50740 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][1]==true && reachable[i][x][1]==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;
            }
        }
    }
    for(int i = 0;i<n;i++) res[i] ^= 1;

    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:279:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |     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 5 ms 1024 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 5 ms 1024 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 356 ms 50612 KB Output is correct
2 Correct 401 ms 50488 KB Output is correct
3 Correct 455 ms 50628 KB Output is correct
4 Correct 1112 ms 50612 KB Output is correct
5 Correct 863 ms 50356 KB Output is correct
6 Correct 736 ms 50228 KB Output is correct
7 Correct 500 ms 50200 KB Output is correct
8 Correct 366 ms 50236 KB Output is correct
9 Correct 401 ms 50316 KB Output is correct
10 Correct 404 ms 50112 KB Output is correct
11 Correct 377 ms 50240 KB Output is correct
12 Correct 92 ms 45900 KB Output is correct
13 Correct 1170 ms 50400 KB Output is correct
14 Correct 1147 ms 50488 KB Output is correct
15 Correct 1150 ms 50484 KB Output is correct
16 Correct 1143 ms 50484 KB Output is correct
17 Correct 1152 ms 50484 KB Output is correct
18 Correct 622 ms 50168 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 50200 KB Output is correct
2 Correct 434 ms 50252 KB Output is correct
3 Correct 695 ms 50356 KB Output is correct
4 Correct 558 ms 50484 KB Output is correct
5 Correct 921 ms 50488 KB Output is correct
6 Correct 810 ms 50488 KB Output is correct
7 Correct 852 ms 50492 KB Output is correct
8 Correct 578 ms 50240 KB Output is correct
9 Correct 101 ms 46412 KB Output is correct
10 Correct 1167 ms 50740 KB Output is correct
11 Correct 1202 ms 50740 KB Output is correct
12 Correct 1179 ms 50740 KB Output is correct
13 Correct 1218 ms 50488 KB Output is correct
14 Correct 765 ms 50500 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 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 5 ms 1024 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 5 ms 1024 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 -