oj.uz

Submission #433931

# Submission time Handle Problem Language Result Execution time Memory
433931 2021-06-20T12:22:03 Z HediChehaidar Traffickers (RMI18_traffickers) C++17
0 / 100
 167 ms 49064 KB 
/*
ID: hedichehaidar
TASK: photo
LANG: C++11
*/
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = INF + 7;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

int n , q , k , t1 , t2;
int ans;
vi adj[1010];
vi path[1010][1010];
set<int> p;
set<pii> s;
vi v;
int d , e;
void dfs(int pos , int par){
    v.pb(pos);
    if(pos == e){
        path[d][e] = v;
        v.pop_back(); return;
    }
    for(auto c : adj[pos]){
        if(c != par) dfs(c , pos);
    }
    v.pop_back();
}
int main() {
    //ifstream fin ("race.in");
    //ofstream fout ("race.out");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i = 0 ; i < n - 1 ; i++){
        int a , b; cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    cin>>k;
    for(int i = 0 ; i < k ; i++) {
        int a , b; cin>>a>>b;
        s.insert({a , b});
    }
    for(auto c : s){
        if(path[c.ff][c.ss].empty()){
            d = c.ff; e = c.ss; dfs(c.ff , -1);
        }
    }
    cin>>q;
   /* for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            if(path[i][j].empty()){
                d = i; e = j;
                dfs(d , -1);
            }
            cout << i << " " << j << "   ";
            for(auto c : path[i][j]) cout << c << " " ; cout << "\n";
        }
    }*/
    while(q--){
        int t , a , b; cin>>t>>a>>b;
        if(t == 1){
            s.insert({a , b});
            if(path[a][b].empty()){
                d = a; e = b; dfs(d , -1);
            }
        }
        else if(t == 2){
            s.erase({a , b});
        }
        else{
            cin>>t1>>t2;
            p.clear();
            if(path[a][b].empty()){
                d = a; e = b; dfs(d , -1);
            }
            for(auto c : path[a][b]) p.insert(c);
            ans = 0;
            for(auto c : s){
                d = c.ff; e = c.ss;
                int nb = path[d][e].size();
                for(int i = t1 ; i <= t2 ; i++){
                    int pos = path[d][e][i % nb];
                    if(p.find(pos) != p.end()) ans++;
                }
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 24300 KB Output isn't correct
2 Incorrect 167 ms 25684 KB Output isn't correct
3 Incorrect 100 ms 24556 KB Output isn't correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 48956 KB Execution killed with signal 11
2 Runtime error 38 ms 48924 KB Execution killed with signal 11
3 Runtime error 55 ms 49028 KB Execution killed with signal 11
4 Runtime error 43 ms 48980 KB Execution killed with signal 11
5 Runtime error 36 ms 49048 KB Execution killed with signal 11
6 Runtime error 36 ms 48992 KB Execution killed with signal 11
7 Runtime error 44 ms 49028 KB Execution killed with signal 11
8 Runtime error 41 ms 49056 KB Execution killed with signal 11
9 Runtime error 39 ms 49020 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 48996 KB Execution killed with signal 11
2 Runtime error 43 ms 49044 KB Execution killed with signal 11
3 Runtime error 43 ms 48972 KB Execution killed with signal 11
4 Runtime error 36 ms 49064 KB Execution killed with signal 11
5 Runtime error 37 ms 48972 KB Execution killed with signal 11
6 Runtime error 35 ms 48992 KB Execution killed with signal 11
7 Runtime error 44 ms 49044 KB Execution killed with signal 11
8 Runtime error 38 ms 48988 KB Execution killed with signal 11