Submission #380235

#	Time	Username	Problem	Language	Result	Execution time	Memory
380235		FatihSolak	Usmjeri (COCI17_usmjeri)	C++17	28 / 140	1559 ms	137812 KiB

usmjeri

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14