oj.uz

Submission #172203

# Submission time Handle Problem Language Result Execution time Memory
172203 2019-12-31T14:55:13 Z HellAngel Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 1609 ms 277432 KB 
/// bai tri tue vai loz cac ban a
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 7;
const int magic = 320;
int n, m, q, dp[maxn], block[maxn];
bool inside[maxn];
vector<int> qr;

vector<int> vt[maxn], vt2[maxn];
vector<pair<int, int>> graph[maxn];
vector<pair<int, int>> newvt = {};

void Add(const pair<int, int> &p)
{
    if(!inside[p.second])
    {
        newvt.push_back(p);
        inside[p.second] = true;
    }
}

void Merge(int x, int y)
{
    int cntx = 0;
    int cnty = 0;
    newvt = {};
    while(cntx < graph[x].size() || cnty < graph[y].size())
    {
        if(newvt.size() == magic) break;
        if(cntx == graph[x].size())
        {
            Add({graph[y][cnty].first + 1, graph[y][cnty].second}), cnty++;
        }
        else if(cnty == graph[y].size()) Add(graph[x][cntx++]);
        else
        {
            if(graph[y][cnty].first + 1 > graph[x][cntx].first)
            {
                Add({graph[y][cnty].first + 1, graph[y][cnty].second});
                cnty++;
            }
            else Add(graph[x][cntx++]);
        }
    }
    graph[x] = newvt;
    for(auto i: graph[x])
    {
        inside[i.second] = 0;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        vt[v].push_back(u);
        vt2[u].push_back(v);
    }
    for(int i = 1; i <= n; i++)
    {
        graph[i].push_back({0, i});
        for(auto j: vt[i])
        {
            Merge(i, j);
        }
    }
    for(int i = 1; i <= q; i++)
    {
        int u, c;
        cin >> u >> c;
        for(int j = 1; j <= c; j++)
        {
            int x;
            cin >> x;
            block[x] = true;
            qr.push_back(x);
        }
        if(c < magic)
        {
            bool ok = false;
            for(int j = 0; j < graph[u].size(); j++)
            {
                if(!block[graph[u][j].second])
                {
                    cout << graph[u][j].first << '\n';
                    ok = true;
                    break;
                }
            }
            if(!ok) cout << -1 << '\n';
        }
        else
        {
            int ans = 0;
            dp[u] = 0;
            for(int j = u - 1; j >= 1; j--)
            {
                dp[j] = -1e9;
                for(auto x: vt2[j])
                {
                    if(x <= u)
                    {
                        dp[j] = max(dp[j], dp[x] + 1);
                    }
                }
                if(!block[j])
                ans = max(ans, dp[j]);
            }
            if(ans > 0)
            {
                cout << ans << '\n';
            }
            else
            {
                if(block[u]) cout << -1 << '\n';
                else cout << 0 << '\n';
            }
        }
        for(auto i: qr) block[i] = 0;
        qr = {};
    }
}

Compilation message

bitaro.cpp: In function 'void Merge(int, int)':
bitaro.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(cntx < graph[x].size() || cnty < graph[y].size())
           ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:30:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(cntx < graph[x].size() || cnty < graph[y].size())
                                     ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cntx == graph[x].size())
            ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if(cnty == graph[y].size()) Add(graph[x][cntx++]);
                 ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:90:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < graph[u].size(); j++)
                            ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:59:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:59:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 16 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 16 ms 14456 KB Output is correct
5 Correct 19 ms 14840 KB Output is correct
6 Correct 18 ms 14840 KB Output is correct
7 Correct 18 ms 14968 KB Output is correct
8 Correct 27 ms 16632 KB Output is correct
9 Correct 27 ms 16632 KB Output is correct
10 Correct 26 ms 16632 KB Output is correct
11 Correct 26 ms 16504 KB Output is correct
12 Correct 21 ms 15480 KB Output is correct
13 Correct 27 ms 16348 KB Output is correct
14 Correct 25 ms 15736 KB Output is correct
15 Correct 21 ms 15096 KB Output is correct
16 Correct 24 ms 15736 KB Output is correct
17 Correct 25 ms 15996 KB Output is correct
18 Correct 22 ms 15480 KB Output is correct
19 Correct 25 ms 15992 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 16 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 16 ms 14456 KB Output is correct
5 Correct 19 ms 14840 KB Output is correct
6 Correct 18 ms 14840 KB Output is correct
7 Correct 18 ms 14968 KB Output is correct
8 Correct 27 ms 16632 KB Output is correct
9 Correct 27 ms 16632 KB Output is correct
10 Correct 26 ms 16632 KB Output is correct
11 Correct 26 ms 16504 KB Output is correct
12 Correct 21 ms 15480 KB Output is correct
13 Correct 27 ms 16348 KB Output is correct
14 Correct 25 ms 15736 KB Output is correct
15 Correct 21 ms 15096 KB Output is correct
16 Correct 24 ms 15736 KB Output is correct
17 Correct 25 ms 15996 KB Output is correct
18 Correct 22 ms 15480 KB Output is correct
19 Correct 25 ms 15992 KB Output is correct
20 Correct 947 ms 20688 KB Output is correct
21 Correct 858 ms 20472 KB Output is correct
22 Correct 927 ms 20476 KB Output is correct
23 Correct 1018 ms 20572 KB Output is correct
24 Correct 1118 ms 178036 KB Output is correct
25 Correct 1202 ms 185032 KB Output is correct
26 Correct 1203 ms 184796 KB Output is correct
27 Correct 1461 ms 276472 KB Output is correct
28 Correct 1463 ms 276348 KB Output is correct
29 Correct 1482 ms 276220 KB Output is correct
30 Correct 1463 ms 275248 KB Output is correct
31 Correct 1445 ms 266620 KB Output is correct
32 Correct 1462 ms 275160 KB Output is correct
33 Correct 1109 ms 177504 KB Output is correct
34 Correct 989 ms 149568 KB Output is correct
35 Correct 1039 ms 176280 KB Output is correct
36 Correct 1219 ms 226828 KB Output is correct
37 Correct 1162 ms 207504 KB Output is correct
38 Correct 1299 ms 227244 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 16 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 16 ms 14456 KB Output is correct
5 Correct 19 ms 14840 KB Output is correct
6 Correct 18 ms 14840 KB Output is correct
7 Correct 18 ms 14968 KB Output is correct
8 Correct 27 ms 16632 KB Output is correct
9 Correct 27 ms 16632 KB Output is correct
10 Correct 26 ms 16632 KB Output is correct
11 Correct 26 ms 16504 KB Output is correct
12 Correct 21 ms 15480 KB Output is correct
13 Correct 27 ms 16348 KB Output is correct
14 Correct 25 ms 15736 KB Output is correct
15 Correct 21 ms 15096 KB Output is correct
16 Correct 24 ms 15736 KB Output is correct
17 Correct 25 ms 15996 KB Output is correct
18 Correct 22 ms 15480 KB Output is correct
19 Correct 25 ms 15992 KB Output is correct
20 Correct 947 ms 20688 KB Output is correct
21 Correct 858 ms 20472 KB Output is correct
22 Correct 927 ms 20476 KB Output is correct
23 Correct 1018 ms 20572 KB Output is correct
24 Correct 1118 ms 178036 KB Output is correct
25 Correct 1202 ms 185032 KB Output is correct
26 Correct 1203 ms 184796 KB Output is correct
27 Correct 1461 ms 276472 KB Output is correct
28 Correct 1463 ms 276348 KB Output is correct
29 Correct 1482 ms 276220 KB Output is correct
30 Correct 1463 ms 275248 KB Output is correct
31 Correct 1445 ms 266620 KB Output is correct
32 Correct 1462 ms 275160 KB Output is correct
33 Correct 1109 ms 177504 KB Output is correct
34 Correct 989 ms 149568 KB Output is correct
35 Correct 1039 ms 176280 KB Output is correct
36 Correct 1219 ms 226828 KB Output is correct
37 Correct 1162 ms 207504 KB Output is correct
38 Correct 1299 ms 227244 KB Output is correct
39 Correct 1191 ms 180812 KB Output is correct
40 Correct 1187 ms 181436 KB Output is correct
41 Correct 1164 ms 182736 KB Output is correct
42 Correct 1289 ms 182400 KB Output is correct
43 Correct 1195 ms 181752 KB Output is correct
44 Correct 964 ms 21880 KB Output is correct
45 Correct 946 ms 21080 KB Output is correct
46 Correct 956 ms 21244 KB Output is correct
47 Correct 1000 ms 20772 KB Output is correct
48 Correct 942 ms 20640 KB Output is correct
49 Correct 1507 ms 276728 KB Output is correct
50 Correct 1344 ms 275576 KB Output is correct
51 Correct 890 ms 21544 KB Output is correct
52 Correct 867 ms 20728 KB Output is correct
53 Correct 1266 ms 226276 KB Output is correct
54 Correct 1227 ms 207868 KB Output is correct
55 Correct 1231 ms 225580 KB Output is correct
56 Correct 1165 ms 207512 KB Output is correct
57 Correct 960 ms 21752 KB Output is correct
58 Correct 990 ms 21680 KB Output is correct
59 Correct 917 ms 20856 KB Output is correct
60 Correct 946 ms 20868 KB Output is correct
61 Correct 1427 ms 275980 KB Output is correct
62 Correct 1325 ms 226640 KB Output is correct
63 Correct 1288 ms 206816 KB Output is correct
64 Correct 1609 ms 275852 KB Output is correct
65 Correct 1502 ms 225596 KB Output is correct
66 Correct 1413 ms 207804 KB Output is correct
67 Correct 1334 ms 275460 KB Output is correct
68 Correct 1228 ms 226164 KB Output is correct
69 Correct 1174 ms 204832 KB Output is correct
70 Correct 1340 ms 276004 KB Output is correct
71 Correct 1248 ms 226704 KB Output is correct
72 Correct 1194 ms 207648 KB Output is correct
73 Correct 1369 ms 276008 KB Output is correct
74 Correct 1271 ms 226736 KB Output is correct
75 Correct 1188 ms 207676 KB Output is correct
76 Correct 1517 ms 277432 KB Output is correct
77 Correct 1324 ms 276064 KB Output is correct
78 Correct 1356 ms 276616 KB Output is correct
79 Correct 900 ms 21688 KB Output is correct
80 Correct 866 ms 20764 KB Output is correct
81 Correct 861 ms 20360 KB Output is correct
82 Correct 1505 ms 276444 KB Output is correct
83 Correct 1492 ms 267672 KB Output is correct
84 Correct 1470 ms 275048 KB Output is correct
85 Correct 1451 ms 266120 KB Output is correct
86 Correct 1481 ms 275528 KB Output is correct
87 Correct 1350 ms 267276 KB Output is correct
88 Correct 972 ms 21808 KB Output is correct
89 Correct 973 ms 21944 KB Output is correct
90 Correct 941 ms 20984 KB Output is correct
91 Correct 1084 ms 21068 KB Output is correct
92 Correct 938 ms 20648 KB Output is correct
93 Correct 927 ms 20544 KB Output is correct
94 Correct 1095 ms 178676 KB Output is correct
95 Correct 997 ms 149768 KB Output is correct
96 Correct 1051 ms 176556 KB Output is correct
97 Correct 975 ms 151024 KB Output is correct
98 Correct 1099 ms 177732 KB Output is correct
99 Correct 986 ms 151116 KB Output is correct
100 Correct 1073 ms 21880 KB Output is correct
101 Correct 1024 ms 21912 KB Output is correct
102 Correct 1026 ms 21008 KB Output is correct
103 Correct 1031 ms 20932 KB Output is correct
104 Correct 1024 ms 20792 KB Output is correct
105 Correct 1047 ms 20692 KB Output is correct
106 Correct 1282 ms 227324 KB Output is correct
107 Correct 1214 ms 208876 KB Output is correct
108 Correct 1277 ms 227484 KB Output is correct
109 Correct 1189 ms 207372 KB Output is correct
110 Correct 1328 ms 228108 KB Output is correct
111 Correct 1169 ms 208632 KB Output is correct
112 Correct 970 ms 21924 KB Output is correct
113 Correct 986 ms 21912 KB Output is correct
114 Correct 933 ms 20828 KB Output is correct
115 Correct 952 ms 21036 KB Output is correct
116 Correct 946 ms 20716 KB Output is correct
117 Correct 961 ms 20580 KB Output is correct
118 Correct 1323 ms 275488 KB Output is correct
119 Correct 1227 ms 226596 KB Output is correct
120 Correct 1160 ms 206700 KB Output is correct
121 Correct 1344 ms 275620 KB Output is correct
122 Correct 1239 ms 225636 KB Output is correct
123 Correct 1162 ms 206864 KB Output is correct
124 Correct 1319 ms 275572 KB Output is correct
125 Correct 1231 ms 226796 KB Output is correct
126 Correct 1150 ms 206056 KB Output is correct