oj.uz

Submission #83865

# Submission time Handle Problem Language Result Execution time Memory
83865 2018-11-11T13:05:56 Z win11905 Bitaro’s Party (JOI18_bitaro) C++11
0 / 100
 113 ms 27288 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 1e5+5;
const int sz = 350;

int n, m, q;
vector<int> g[N], topo;
vector<pii> block[N];
int pos[N], deg[N];
int d[N];
map<int, int> tod[N];
bool mark[N];

int main() {
    scanf("%d %d %d", &n, &m, &q);
    for(int i = 0, u, v; i < m; ++i) {
        scanf("%d %d", &u, &v);
        if(u > v) swap(u, v);
        g[u].emplace_back(v);
        deg[v]++;
    }
    queue<int> Q;
    for(int i = 1; i <= n; ++i) if(!deg[i]) Q.emplace(i);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        topo.emplace_back(u);
        for(auto x : tod[u]) block[u].emplace_back(x);
        block[u].emplace_back(u, 0);
        sort(all(block[u]), [&](const pii &a, const pii &b) { return a.y > b.y; });
        if(block[u].size() > sz) block[u].resize(sz);
        for(int v : g[u]) {
            for(pii x : block[u]) tod[v][x.x] = max(tod[v][x.x], x.y + 1);
            if(!--deg[v]) Q.emplace(v);
        }    
    }
    for(int i = 0, u, t; i < q; ++i) {
        scanf("%d %d", &u, &t);
        vector<int> vec;
        for(int i = 0, v; i < t; ++i) scanf("%d", &v), vec.emplace_back(v);
        if(t < sz) {
            for(int v : vec) mark[v] ^= 1;
            bool st = true;
            for(pii v : block[u]) if(!mark[v.x]) {
                printf("%d\n", v.y), st = false;
                break;
            }
            if(st) puts("-1");
            for(int v : vec) mark[v] ^= 1;
        } else {
            memset(d, 0, sizeof d);
            for(int v : vec) d[v] = -1e9;
            for(int i = 0; i < n; ++i) {
                int u = topo[i];
                for(int v : g[u]) d[v] = max(d[v], d[u] + 1);
            }
            printf("%d\n", d[u]);
        }
    } 
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &t);
         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:44:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i = 0, v; i < t; ++i) scanf("%d", &v), vec.emplace_back(v);
                                       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9896 KB Output is correct
3 Correct 11 ms 9896 KB Output is correct
4 Correct 11 ms 9896 KB Output is correct
5 Correct 27 ms 12440 KB Output is correct
6 Correct 26 ms 12516 KB Output is correct
7 Correct 24 ms 12516 KB Output is correct
8 Correct 96 ms 27172 KB Output is correct
9 Correct 95 ms 27176 KB Output is correct
10 Correct 87 ms 27288 KB Output is correct
11 Correct 111 ms 27288 KB Output is correct
12 Correct 58 ms 27288 KB Output is correct
13 Incorrect 113 ms 27288 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9896 KB Output is correct
3 Correct 11 ms 9896 KB Output is correct
4 Correct 11 ms 9896 KB Output is correct
5 Correct 27 ms 12440 KB Output is correct
6 Correct 26 ms 12516 KB Output is correct
7 Correct 24 ms 12516 KB Output is correct
8 Correct 96 ms 27172 KB Output is correct
9 Correct 95 ms 27176 KB Output is correct
10 Correct 87 ms 27288 KB Output is correct
11 Correct 111 ms 27288 KB Output is correct
12 Correct 58 ms 27288 KB Output is correct
13 Incorrect 113 ms 27288 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9896 KB Output is correct
3 Correct 11 ms 9896 KB Output is correct
4 Correct 11 ms 9896 KB Output is correct
5 Correct 27 ms 12440 KB Output is correct
6 Correct 26 ms 12516 KB Output is correct
7 Correct 24 ms 12516 KB Output is correct
8 Correct 96 ms 27172 KB Output is correct
9 Correct 95 ms 27176 KB Output is correct
10 Correct 87 ms 27288 KB Output is correct
11 Correct 111 ms 27288 KB Output is correct
12 Correct 58 ms 27288 KB Output is correct
13 Incorrect 113 ms 27288 KB Output isn't correct
14 Halted 0 ms 0 KB -