oj.uz

Submission #567344

# Submission time Handle Problem Language Result Execution time Memory
567344 2022-05-23T10:43:34 Z Majid Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 63876 KB 
#include<bits/stdc++.h>
using namespace std;
 
//Types
using ll = long long;
using db = double;
 
//Vectors
#define pb push_back
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(), vec.end()
 
//things
#define f first
#define s second
const int SMALLINF = 1e9 + 7;
const ll BIGINF = ((ll)1e18) + 7;
#define Speeed ios::sync_with_stdio(0);cin.tie(NULL); cout.tie(NULL);

vector<ll> connect[20007];
// map<ll, map<ll, ll> > dist;
map<ll, ll> dist;
map<ll, bool> visited;
map<ll, map<ll, ll> > ans;
deque<ll> top;

void dfs(ll x){
    
    visited[x] = true;
    
    for(auto y: connect[x]){
        
            if(!visited[y]){
                
                dfs(y);
            }
            
            // path[x] = max(path[x], path[y]+1);
    }
    
    top.pb(x);
    
}

void solve(){

    ll n, m, q;
    cin>>n>>m>>q;
    
    for(ll i = 0; i < m; i++){
        
        ll u, v;
        cin>>u>>v;
        connect[u].pb(v);
        // connect[v].pb(u);
    }
    
    for(ll i = 1; i <= n; i++){
        
        if(!visited[i])dfs(i);
    }
    
    for(ll i = 1; i <= n; i++){
        
        for(ll j = 1; j <= n; j++){
            
            if(i!=j)dist[j] = BIGINF;
        }
        
        dist[i] = 0;
        deque<ll> top2 = top;
        while (!top2.empty()){
            
            ll u = top2.back();
            top2.pop_back();
            // cout<<u<<" ";
            if (dist[u]!=BIGINF){
                
                for (auto v : connect[u]){
                    
                    if (dist[v] > dist[u] - 1){
                        
                        dist[v] = dist[u] - 1;
                        // cout<<"here: "<<dist[v]<<" "<<dist[u]<<"\n";
                    }
                }
            }
        }
        
        // cout<<i<<": ";
        for(ll k = 1; k <= n; k++){
            
            ans[i][k] = dist[k]*-1;
            // if(dist[k]==BIGINF)cout<<"! ";
            // else cout<<dist[k]*-1<<" ";
            dist[k] = 0;
        }
        // cout<<"\n";
    }

    
    while(q--){
    
        ll t, y;
        cin>>t>>y;
        map<ll, bool> no;
    
        for(ll i = 0; i < y; i++){
    
            ll x;
            cin>>x;
            no[x] = true;
        }
    
        ll mx = -1;
    
        for(ll i = 1; i <= n; i++){
    
            if(!no[i]){
    
                mx = max(mx, ans[i][t]);
                // cout<<i<<" "<<dist[i][t]<<"\n";
            }
        }
        cout<<mx<<" ";
    }

     
}

int main(){
	Speeed
	
    ll t=1;
    // cin>>t;
    
    while(t--){
        
        solve();
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 384 ms 63772 KB Output is correct
6 Correct 370 ms 63780 KB Output is correct
7 Correct 393 ms 63772 KB Output is correct
8 Correct 492 ms 63876 KB Output is correct
9 Correct 528 ms 63868 KB Output is correct
10 Correct 506 ms 63872 KB Output is correct
11 Correct 471 ms 63776 KB Output is correct
12 Correct 394 ms 63776 KB Output is correct
13 Correct 495 ms 63672 KB Output is correct
14 Correct 509 ms 63772 KB Output is correct
15 Correct 434 ms 63776 KB Output is correct
16 Correct 470 ms 63768 KB Output is correct
17 Correct 460 ms 63708 KB Output is correct
18 Correct 380 ms 63716 KB Output is correct
19 Correct 469 ms 63740 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 384 ms 63772 KB Output is correct
6 Correct 370 ms 63780 KB Output is correct
7 Correct 393 ms 63772 KB Output is correct
8 Correct 492 ms 63876 KB Output is correct
9 Correct 528 ms 63868 KB Output is correct
10 Correct 506 ms 63872 KB Output is correct
11 Correct 471 ms 63776 KB Output is correct
12 Correct 394 ms 63776 KB Output is correct
13 Correct 495 ms 63672 KB Output is correct
14 Correct 509 ms 63772 KB Output is correct
15 Correct 434 ms 63776 KB Output is correct
16 Correct 470 ms 63768 KB Output is correct
17 Correct 460 ms 63708 KB Output is correct
18 Correct 380 ms 63716 KB Output is correct
19 Correct 469 ms 63740 KB Output is correct
20 Execution timed out 2057 ms 8136 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 384 ms 63772 KB Output is correct
6 Correct 370 ms 63780 KB Output is correct
7 Correct 393 ms 63772 KB Output is correct
8 Correct 492 ms 63876 KB Output is correct
9 Correct 528 ms 63868 KB Output is correct
10 Correct 506 ms 63872 KB Output is correct
11 Correct 471 ms 63776 KB Output is correct
12 Correct 394 ms 63776 KB Output is correct
13 Correct 495 ms 63672 KB Output is correct
14 Correct 509 ms 63772 KB Output is correct
15 Correct 434 ms 63776 KB Output is correct
16 Correct 470 ms 63768 KB Output is correct
17 Correct 460 ms 63708 KB Output is correct
18 Correct 380 ms 63716 KB Output is correct
19 Correct 469 ms 63740 KB Output is correct
20 Execution timed out 2057 ms 8136 KB Time limit exceeded
21 Halted 0 ms 0 KB -