oj.uz

Submission #154384

# Submission time Handle Problem Language Result Execution time Memory
154384 2019-09-21T15:29:22 Z PedroBigMan Usmjeri (COCI17_usmjeri) C++14
0 / 140
 2000 ms 144940 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define INF ((ll) pow(2,63) -1)
#define si signed
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
ll mod = 1000000007;

class Graph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<ll> visited; //for DFS
    vector<ll> current; //for CC
    
    Graph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
    }
    
    void DFS(ll s)
    {
        if(visited[s]) {return;}
        visited[s]=true;
        current.pb(s); 
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {DFS(adj[s][i]);}
        }
        return;
    }
    
    vector<vector<ll> > CC()
    {
        ll fi=0; ll missing=N; REP(i,0,N) {visited[i]=false;}
        vector<vector<ll> > ans;
        while(missing>0)
        {
            REP(i,fi,N) {if(!visited[i]) {fi=i; break;}}
            current.clear();
            DFS(fi);
            ans.pb(current);
            missing-=current.size();
        }
        return ans;
    }
    
};

class Tree
{
    public:
    ll N; 
    vector<vector<ll> > adj;
    vector<ll> cu; 
    map<pl,ll> ed;
    ll target; vector<ll> ans;
    
    Tree(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); ll cured=0;
        REP(i,0,N)
        {
            REP(j,0,adj[i].size()) 
            {
                if(adj[i][j]>i) {continue;}
                ed.insert(mp(mp(i,adj[i][j]),cured));
                ed.insert(mp(mp(adj[i][j],i),cured));
                cured++;
            }
        }
    }
    
    void DFS(ll s, ll p)
    {
        if(ans.size()>0) {return;}
        if(s==target) {ans.clear(); ans=cu; return;}
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==p) {continue;}
            cu.pb(ed[mp(s,adj[s][i])]);
            DFS(adj[s][i],s);
            cu.pop_back();
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll N,M; cin>>N>>M; 
    vector<vector<ll> > adja; vector<ll> xx; REP(i,0,N) {adja.pb(xx);}
    ll cur1,cur2;
    REP(i,0,N-1) {cin>>cur1>>cur2; cur1--; cur2--; adja[cur1].pb(cur2); adja[cur2].pb(cur1);}
    vector<pl> t; REP(i,0,M) {cin>>cur1>>cur2; cur1--; cur2--; t.pb(mp(cur1,cur2));}
    Tree T(adja);
    vector<vector<ll> > gr;
    REP(i,0,M)
    {
        T.target=t[i].ss;
        T.DFS(t[i].ff,-1);
        gr.pb(T.ans);
        T.ans.clear();
        T.cu.clear();
    }
    vector<vector<ll> > adj; REP(i,0,N-1) {adj.pb(xx);}
    REP(i,0,gr.size())
    {
        REP(j,0,gr[i].size()-1)
        {
            adj[gr[i][j]].pb(gr[i][j+1]);
            adj[gr[i][j+1]].pb(gr[i][j]);
        }
    }
    Graph G(adj);
    vector<vector<ll> > Con = G.CC();
    ll sum=0;
    REP(i,0,Con.size()) {sum+=Con[i].size();}
    ll id=1;
    REP(i,0,N-1-sum+Con.size()) {id*=2; id%=mod;}
    cout<<id<<endl;
    return 0;
}

Compilation message

usmjeri.cpp: In function 'void Out(std::vector<long long int>)':
usmjeri.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
usmjeri.cpp:21:29:
 void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
                             ~~~~~~~~~~~~
usmjeri.cpp:21:25: note: in expansion of macro 'REP'
 void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
                         ^~~
usmjeri.cpp: In member function 'void Graph::DFS(ll)':
usmjeri.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
usmjeri.cpp:42:13:
         REP(i,0,adj[s].size())
             ~~~~~~~~~~~~~~~~~    
usmjeri.cpp:42:9: note: in expansion of macro 'REP'
         REP(i,0,adj[s].size())
         ^~~
usmjeri.cpp: In constructor 'Tree::Tree(std::vector<std::vector<long long int> >)':
usmjeri.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
usmjeri.cpp:80:17:
             REP(j,0,adj[i].size()) 
                 ~~~~~~~~~~~~~~~~~
usmjeri.cpp:80:13: note: in expansion of macro 'REP'
             REP(j,0,adj[i].size()) 
             ^~~
usmjeri.cpp: In member function 'void Tree::DFS(ll, ll)':
usmjeri.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
usmjeri.cpp:94:13:
         REP(i,0,adj[s].size())
             ~~~~~~~~~~~~~~~~~    
usmjeri.cpp:94:9: note: in expansion of macro 'REP'
         REP(i,0,adj[s].size())
         ^~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
usmjeri.cpp:124:9:
     REP(i,0,gr.size())
         ~~~~~~~~~~~~~            
usmjeri.cpp:124:5: note: in expansion of macro 'REP'
     REP(i,0,gr.size())
     ^~~
usmjeri.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
usmjeri.cpp:126:13:
         REP(j,0,gr[i].size()-1)
             ~~~~~~~~~~~~~~~~~~   
usmjeri.cpp:126:9: note: in expansion of macro 'REP'
         REP(j,0,gr[i].size()-1)
         ^~~
usmjeri.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
usmjeri.cpp:135:9:
     REP(i,0,Con.size()) {sum+=Con[i].size();}
         ~~~~~~~~~~~~~~           
usmjeri.cpp:135:5: note: in expansion of macro 'REP'
     REP(i,0,Con.size()) {sum+=Con[i].size();}
     ^~~
usmjeri.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
usmjeri.cpp:137:9:
     REP(i,0,N-1-sum+Con.size()) {id*=2; id%=mod;}
         ~~~~~~~~~~~~~~~~~~~~~~   
usmjeri.cpp:137:5: note: in expansion of macro 'REP'
     REP(i,0,N-1-sum+Con.size()) {id*=2; id%=mod;}
     ^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 110484 KB Time limit exceeded

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2025 ms 144940 KB Time limit exceeded

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 848 KB Output is correct
2 Incorrect 313 ms 1296 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 760 KB Output is correct
2 Incorrect 305 ms 1272 KB Output isn't correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2008 ms 2104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 1976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2109 ms 102164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 102176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 ms 102300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 102392 KB Time limit exceeded
2 Halted 0 ms 0 KB -