Submission #1073381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073381		Requiem	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1281 ms	416048 KiB

bitaro

#include<bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define endl '\n'
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define int long long
#define TASKNAME "Bitaro"
using namespace std;
typedef pair<int, int> ii;
template<typename T> bool maximize(T &a, T b) { if (a < b) {a = b; return true;} return false; }
/**
Cho đồ thị có hướng n đỉnh
Mỗi cạnh luôn nối từ đỉnh có chỉ số nhỏ hơn đến đỉnh có chỉ số lớn hơn.

Cho q truy vấn:
Truy vấn thứ i cho ta Ti, Yi và tập S gồm Yi đỉnh.
Tức là ta cần tìm đường đi dài nhất đến S từ 1 đỉnh không nằm trong tập S.
Tổng Y1 + Y2 + ... + Yq <= 1e5.
sub1 và 2: dp dag.

sub3:
Ta đảo chiều cạnh.
Xong ta xuất phát từ Ti đi đến tất cả các đỉnh. Từ đó ta có thể tìm được đường đi xa nhất
xuất phát từ i.

Ban đầu ta rõ ràng có thể tính được khoảng cách xa nhất đến tất cả các đỉnh vì đây là dag nhưng
có những đỉnh ta không được phép đi qua.

Giả sử ta chỉ giải quyết cho đỉnh u thì sao.

Với những truy vấn mà bận nhiều hơn sqrt(1e5) đỉnh thì nó chỉ có tối đa sqrt(1e5) như vậy thì ta
có thể giải trực tiếp cho sqrt(n) đỉnh đó.

Với những đỉnh ít hơn sqrt(n) đỉnh thì ta có thể duyệt qua sqrt(n) đường đi nhỏ nhất xuất phát từ các đỉnh
khác nhau đến u.

Bây giờ ta tìm B đường đi ngắn nhất từ u. Ta co the tim tu phai sang trai.
**/

const int MAXN = 1e5 + 9;
const int B = 137;
vector<int> g[MAXN];
vector<int> topo;

vector<ii> listPath[MAXN]; //chua idx va len.
int from[MAXN], Orijin[MAXN], dp[MAXN], deg[MAXN];
int n, m, q;
void buildTopo(){
    queue<int> q;
    FOR(i, 0, n - 1){
        if (deg[i] == 0) q.push(i);
    }
    while(!q.empty()){
        int u = q.front();
        topo.pb(u);
        q.pop();
        for(auto v: g[u]){
            deg[v]--;
            if (deg[v] == 0) q.push(v);
        }
    }
}

int solve1(int u){
    int ans = -1;
    for(auto [id, len]: listPath[u]){
        if (!Orijin[id]) {
            ans = len;
            break;
        }
    }
    return ans;
}

int solve2(int c){

    FOR(i, 0, n - 1) dp[i] = -1e9;
    dp[c] = 0;
    int ans = -1;
    FOR(i, 0, (int)topo.size() - 1) {
         int u = topo[i];
         for(auto v: g[u]){
             maximize(dp[v], dp[u] + 1);
         }
    }
    FOR(i, 0, n - 1){
        if (!Orijin[i]) maximize(ans, dp[i]);
    }
    return ans;
}
main(){
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> m >> q;
    FOR(i, 0, m - 1){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[v].pb(u);
        deg[u]++;
    }
    FOR(i, 0, n - 1){
        vector<int> cur;
        cur.pb(i);
        from[i] = 0;
        for(auto v: g[i]){
            for(auto [id, len]: listPath[v]){
                if (!from[id]) {
                    from[id] = len + 1;
                    cur.pb(id);
                }
                else{
                    maximize(from[id], len + 1);
                }
            }
        }
        sort(cur.begin(), cur.end(), [&](const int &a, const int &b){
             return from[a] > from[b];
        });

        while(cur.size() > B) {from[cur.back()] = 0; cur.pop_back(); };
        for(auto id: cur){
            listPath[i].pb(ii(id, from[id]));
            from[id] = 0;
        }
        cur.clear();
    }

    buildTopo();

    vector<int> listBusy;
    FOR(i, 0, q - 1){
        int c, numBusy;
        cin >> c >> numBusy;
        c--;
        FOR(j, 0, numBusy - 1){
            int x;
            cin >> x;
            x--;
            listBusy.pb(x);
            Orijin[x] = true;
        }

        if (numBusy < B){
            printf("%lld\n", solve1(c));
        }
        else{
            printf("%lld\n", solve2(c));
        }

        FOR(j, 0, numBusy - 1) Orijin[listBusy[j]] = false;
        listBusy.clear();

    }
}

Compilation message (stderr)

bitaro.cpp:92:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main(){
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86