oj.uz

Submission #433985

# Submission time Handle Problem Language Result Execution time Memory
433985 2021-06-20T13:22:35 Z AmineTrabelsi Traffickers (RMI18_traffickers) C++14
0 / 100
 1123 ms 640 KB 
#include "bits/stdc++.h"
using namespace std;
// Hi 
int n;
vector<int> gr[5005];
set<pair<int,int>> traf;
vector<int> path;
void dfs(int u,int par,int v){
    if(u == v){
        path.push_back(v);
        return;
    }
    for(auto i:gr[u]){
        if(i != par){
            dfs(i,u,v);
            if(!path.empty())break;
        }
    }
    if(!path.empty())path.push_back(u);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        traf.insert({x,y});
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t == 1){
            int x,y;
            cin>>x>>y;
            x--,y--;
            traf.insert({x,y});
        }else if(t == 2){
            int x,y;
            cin>>x>>y;
            x--,y--;
            traf.erase({x,y});
        }else{
            int x,y,l,r;
            cin>>x>>y>>l>>r;
            x--,y--;
            vector<int> cnt(n+1,0);
            for(auto i:traf){
                path.clear();
                dfs(i.first,-1,i.second);
                reverse(path.begin(),path.end());
                /*
                for(auto pp:path)cout << pp <<" ";
                    cout << '\n';*/
                int pos = 0;
                int p = path.size();
                for(int xx=0;xx<=r;xx++){
                    if(xx>=l)cnt[path[pos]]++;
                    if(pos == p-1)pos = 0;
                    else pos++;
                }
            }
            path.clear();
            dfs(x,-1,y);
            reverse(path.begin(),path.end());
            int ans = 0;
            for(auto i:path)ans += cnt[i];
                cout << ans << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Incorrect 929 ms 520 KB Output isn't correct
3 Incorrect 1123 ms 504 KB Output isn't correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 11
2 Runtime error 1 ms 588 KB Execution killed with signal 11
3 Runtime error 1 ms 588 KB Execution killed with signal 11
4 Runtime error 1 ms 588 KB Execution killed with signal 11
5 Runtime error 1 ms 588 KB Execution killed with signal 11
6 Runtime error 1 ms 588 KB Execution killed with signal 11
7 Runtime error 1 ms 588 KB Execution killed with signal 11
8 Runtime error 1 ms 588 KB Execution killed with signal 11
9 Runtime error 1 ms 588 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 11
2 Runtime error 1 ms 588 KB Execution killed with signal 11
3 Runtime error 1 ms 640 KB Execution killed with signal 11
4 Runtime error 1 ms 588 KB Execution killed with signal 11
5 Runtime error 1 ms 588 KB Execution killed with signal 11
6 Runtime error 2 ms 588 KB Execution killed with signal 11
7 Runtime error 1 ms 588 KB Execution killed with signal 11
8 Runtime error 2 ms 604 KB Execution killed with signal 11