oj.uz

Submission #200569

# Submission time Handle Problem Language Result Execution time Memory
200569 2020-02-07T11:38:16 Z stefdasca Tenis (COI19_tenis) C++14
39 / 100
 500 ms 21576 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, q;
int ord[4][100002], poz[4][100002];

int nr;
bool viz[100002], viz2[100002];
vector<int>v[100002], tr[100002];
stack<int>s;
void dfs(int nod)
{
    viz[nod] = 1;
    for(int j = 0; j < v[nod].size(); ++j)
    {
        int vecin = v[nod][j];
        if(!viz[vecin])
            dfs(vecin);
    }
    s.push(nod);
}
bool bst[100002];

void dfs2(int nod)
{
    viz2[nod] = 1;
    if(nr == 1)
        bst[nod] = 1;
    for(int j = 0; j < tr[nod].size(); ++j)
    {
        int vecin = tr[nod][j];
        if(!viz2[vecin])
            dfs2(vecin);
    }
}


void build()
{
    nr = 0;
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            dfs(i);
    while(!s.empty())
    {
        int nod = s.top();
        s.pop();
        if(!viz2[nod])
        {
            ++nr;
            dfs2(nod);
        }
    }
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for(int j = 1; j <= 3; ++j)
    {
        for(int i = 1; i <= n; ++i)
            cin >> ord[j][i], poz[j][ord[j][i]] = i;
        for(int i = 1; i < n; ++i)
        {
            v[ord[j][i]].pb(ord[j][i+1]);
            tr[ord[j][i+1]].pb(ord[j][i]);
        }
    }
    build();
    for(; q; --q)
    {
        int tip, val;
        cin >> tip;
        if(tip == 1)
        {
            cin >> val;
            cout << (bst[val] ? "DA" : "NE") << '\n';
        }
        else
        {
            int wh, a, b;
            cin >> wh >> a >> b;
            int x = poz[wh][a];
            int y = poz[wh][b];
            swap(ord[wh][x], ord[wh][y]);
            swap(poz[wh][a], poz[wh][b]);
            for(int j = 1; j <= n; ++j)
                v[j].clear(), tr[j].clear(), bst[j] = 0, viz[j] = viz2[j] = 0;
            for(int j = 1; j <= 3; ++j)
                for(int i = 1; i < n; ++i)
                {
                    v[ord[j][i]].pb(ord[j][i+1]);
                    tr[ord[j][i+1]].pb(ord[j][i]);
                }
            build();
        }
    }
    return 0;
}

Compilation message

tenis.cpp: In function 'void dfs(int)':
tenis.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < v[nod].size(); ++j)
                    ~~^~~~~~~~~~~~~~~
tenis.cpp: In function 'void dfs2(int)':
tenis.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < tr[nod].size(); ++j)
                    ~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 8 ms 5240 KB Output is correct
8 Correct 9 ms 5240 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 17 ms 5240 KB Output is correct
11 Correct 9 ms 5240 KB Output is correct
12 Correct 9 ms 5240 KB Output is correct
13 Correct 465 ms 20728 KB Output is correct
14 Execution timed out 669 ms 19256 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 16968 KB Output is correct
2 Correct 169 ms 19272 KB Output is correct
3 Correct 161 ms 20424 KB Output is correct
4 Correct 154 ms 21576 KB Output is correct
5 Correct 180 ms 19140 KB Output is correct
6 Correct 158 ms 20168 KB Output is correct
7 Correct 163 ms 18888 KB Output is correct
8 Correct 173 ms 20680 KB Output is correct
9 Correct 163 ms 20456 KB Output is correct
10 Correct 163 ms 20040 KB Output is correct
11 Correct 169 ms 19140 KB Output is correct
12 Correct 165 ms 21064 KB Output is correct
13 Correct 188 ms 20424 KB Output is correct
14 Correct 163 ms 21048 KB Output is correct
15 Correct 159 ms 21564 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 8 ms 5240 KB Output is correct
8 Correct 9 ms 5240 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 17 ms 5240 KB Output is correct
11 Correct 9 ms 5240 KB Output is correct
12 Correct 9 ms 5240 KB Output is correct
13 Correct 465 ms 20728 KB Output is correct
14 Execution timed out 669 ms 19256 KB Time limit exceeded
15 Halted 0 ms 0 KB -