oj.uz

Submission #380235

# Submission time Handle Problem Language Result Execution time Memory
380235 2021-03-20T16:08:29 Z FatihSolak Usmjeri (COCI17_usmjeri) C++17
28 / 140
 1559 ms 137812 KB 
#include <bits/stdc++.h>
#define N       300005
#define mod     1000000007
using namespace std;
vector<int> adj[N];
vector<int> adj2[N];
map<pair<int,int>,int> col;
set<pair<int,int>> s[N];
bool vis[N];
int pr[N];
void dfs(int v,int par){
    vector<pair<int,int>> sz;
    pr[v] = par; 
    sz.push_back({0,0});
    for(auto u:adj[v]){
        if(u == par)continue;
        dfs(u,v);
        sz.push_back({s[u].size(),u});
    }
    sort(sz.rbegin(),sz.rend());
    swap(s[v],s[sz[0].second]);
    for(int i=1;i<sz.size();i++){
        for(auto u:s[sz[i].second]){
            u = {min(u.first,u.second),max(u.first,u.second)};
            if(s[v].count(u)){
                s[v].erase(u);
            }
            else s[v].insert(u);
        }
    }
    for(auto u:adj2[v]){
        pair<int,int> tmp = {min(u,v),max(u,v)};
        if(s[v].count(tmp)){
                s[v].erase(tmp);
        }
        else s[v].insert(tmp);
    }
    /*
    cout << v << endl;
    for(auto u:s[v]){
        cout << u.first << " " << u.second << " " ;
    }
    cout << endl;*/
    col[{v,par}] = !!s[v].size() + 1;
}
void solve(){
    int n,m;
    cin >> n >> m;
    vector<pair<int,int>> edge;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edge.push_back({u,v});
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        adj2[u].push_back(v);
        adj2[v].push_back(u);
    }
    dfs(1,0);
    long long ans = 1;
    //cout << col[{1,0}]<<endl;
    for(auto u:edge){
        if(!col[u])swap(u.first,u.second);
        //cout << u.first << " " << u.second << endl;
        //cout << col[u] << endl;
        if(col[u] == 1)ans = ans*2%mod;
        else if(!vis[u.second] && col[{u.second,pr[u.second]}] == 1){
            vis[u.second] = 1;
            ans = ans*2%mod;
        }
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

usmjeri.cpp: In function 'void dfs(int, int)':
usmjeri.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=1;i<sz.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 68056 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 137812 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 28780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 28780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 29804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 29672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1461 ms 111932 KB Output is correct
2 Correct 1433 ms 115540 KB Output is correct
3 Incorrect 794 ms 79880 KB Output isn't correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1494 ms 120192 KB Output is correct
2 Correct 1528 ms 120020 KB Output is correct
3 Incorrect 1008 ms 101076 KB Output isn't correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1443 ms 116796 KB Output is correct
2 Correct 1482 ms 119964 KB Output is correct
3 Incorrect 997 ms 95324 KB Output isn't correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1559 ms 126708 KB Output is correct
2 Correct 1439 ms 126008 KB Output is correct
3 Incorrect 876 ms 75740 KB Output isn't correct