oj.uz

Submission #200570

# Submission time Handle Problem Language Result Execution time Memory
200570 2020-02-07T11:39:49 Z stefdasca Tenis (COI19_tenis) C++14
51 / 100
 500 ms 21064 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();
    bool oki = 1;
    for(; q; --q)
    {
        int tip, val;
        cin >> tip;
        if(tip == 1)
        {
            if(!oki)
            {
                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();
                oki = 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]);
            oki = 0;
        }
    }
    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 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 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 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 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 8 ms 5240 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Correct 8 ms 5240 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 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 8 ms 5240 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Correct 8 ms 5240 KB Output is correct
13 Correct 263 ms 19992 KB Output is correct
14 Correct 318 ms 16984 KB Output is correct
15 Correct 236 ms 20888 KB Output is correct
16 Correct 171 ms 18760 KB Output is correct
17 Correct 145 ms 19012 KB Output is correct
18 Correct 151 ms 19268 KB Output is correct
19 Correct 187 ms 19228 KB Output is correct
20 Correct 133 ms 18808 KB Output is correct
21 Correct 164 ms 21064 KB Output is correct
22 Correct 160 ms 20472 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 16200 KB Output is correct
2 Correct 144 ms 17864 KB Output is correct
3 Correct 147 ms 17864 KB Output is correct
4 Correct 153 ms 19144 KB Output is correct
5 Correct 144 ms 16580 KB Output is correct
6 Correct 143 ms 17736 KB Output is correct
7 Correct 153 ms 16456 KB Output is correct
8 Correct 149 ms 18120 KB Output is correct
9 Correct 154 ms 17864 KB Output is correct
10 Correct 148 ms 17480 KB Output is correct
11 Correct 150 ms 16708 KB Output is correct
12 Correct 145 ms 18504 KB Output is correct
13 Correct 155 ms 17992 KB Output is correct
14 Correct 143 ms 18504 KB Output is correct
15 Correct 160 ms 19012 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 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 8 ms 5240 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Correct 8 ms 5240 KB Output is correct
13 Correct 263 ms 19992 KB Output is correct
14 Correct 318 ms 16984 KB Output is correct
15 Correct 236 ms 20888 KB Output is correct
16 Correct 171 ms 18760 KB Output is correct
17 Correct 145 ms 19012 KB Output is correct
18 Correct 151 ms 19268 KB Output is correct
19 Correct 187 ms 19228 KB Output is correct
20 Correct 133 ms 18808 KB Output is correct
21 Correct 164 ms 21064 KB Output is correct
22 Correct 160 ms 20472 KB Output is correct
23 Correct 158 ms 16200 KB Output is correct
24 Correct 144 ms 17864 KB Output is correct
25 Correct 147 ms 17864 KB Output is correct
26 Correct 153 ms 19144 KB Output is correct
27 Correct 144 ms 16580 KB Output is correct
28 Correct 143 ms 17736 KB Output is correct
29 Correct 153 ms 16456 KB Output is correct
30 Correct 149 ms 18120 KB Output is correct
31 Correct 154 ms 17864 KB Output is correct
32 Correct 148 ms 17480 KB Output is correct
33 Correct 150 ms 16708 KB Output is correct
34 Correct 145 ms 18504 KB Output is correct
35 Correct 155 ms 17992 KB Output is correct
36 Correct 143 ms 18504 KB Output is correct
37 Correct 160 ms 19012 KB Output is correct
38 Execution timed out 1060 ms 18892 KB Time limit exceeded
39 Halted 0 ms 0 KB -