oj.uz

Submission #110955

# Submission time Handle Problem Language Result Execution time Memory
110955 2019-05-13T10:53:22 Z igzi Mergers (JOI19_mergers) C++17
0 / 100
 117 ms 36468 KB 
#include <bits/stdc++.h>
#define maxN 500005

using namespace std;

vector <int> v,adj[maxN],g[maxN];
long long x,y,i,n,k,c[maxN],l[maxN],d[maxN],s[maxN],a[maxN];
bool b[maxN];

void dfs(int n,int par){
int i;
v.push_back(c[n]);
l[n]=v.size()-1;
d[n]=v.size()-1;
for(i=0;i<adj[n].size();i++){
    if(adj[n][i]!=par){
        dfs(adj[n][i],n);
        d[n]=d[adj[n][i]];
    }
}
}

void dfs1(int n,int par){
long long tmp,i;
if(l[n]==0) tmp=0;
else tmp=s[l[n]-1];
if(par!=-1 && s[d[n]]^tmp!=0){
g[n].push_back(par);
g[par].push_back(n);
}
for(i=0;i<adj[n].size();i++){
    if(adj[n][i]!=par){
        dfs1(adj[n][i],n);
    }
}
}

void dfs2(int n){
int i;
b[n]=true;
x+=adj[n].size()-g[n].size();
for(i=0;i<g[n].size();i++){
    if(!b[g[n][i]]){
        dfs2(g[n][i]);
    }
}
}

int main()
{
    srand(time(NULL));
    std::ios_base::sync_with_stdio(0);
    cin>>n>>k;
    for(i=1;i<n;i++){
        cin>>x>>y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(i=0;i<n;i++){
        cin>>c[i];
        c[i]--;
    }
    dfs(0,-1);
    for(i=0;i<n;i++){
        a[i]=rand()+(rand()<<32);
    }
    for(i=0;i<v.size();i++){
        if(!b[v[i]]){
            s[i]^=a[v[i]];
            b[v[i]]=true;
        }
    }
    memset(b,false,n);
    for(i=v.size()-1;i>=0;i--){
        if(!b[v[i]]){
            s[i]^=a[v[i]];
            b[v[i]]=true;
        }
    }
    for(i=1;i<n;i++){
        s[i]^=s[i-1];
    }
    dfs1(0,-1);
    memset(b,false,n);
    y=0;
    for(i=0;i<n;i++){
        if(!b[i]){
            x=0;
            dfs2(i);
            if(x==1) y++;
        }
    }
    cout<<(y+1)/2<<endl;
    return 0;
}

Compilation message

mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:15:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
         ~^~~~~~~~~~~~~~
mergers.cpp: In function 'void dfs1(int, int)':
mergers.cpp:27:26: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
 if(par!=-1 && s[d[n]]^tmp!=0){
                       ~~~^~~
mergers.cpp:31:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
         ~^~~~~~~~~~~~~~
mergers.cpp: In function 'void dfs2(int)':
mergers.cpp:42:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<g[n].size();i++){
         ~^~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:67:30: warning: left shift count >= width of type [-Wshift-count-overflow]
         a[i]=rand()+(rand()<<32);
                              ^~
mergers.cpp:69:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<v.size();i++){
             ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Incorrect 23 ms 23928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Incorrect 23 ms 23928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Incorrect 23 ms 23928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 36468 KB Output is correct
2 Correct 117 ms 33024 KB Output is correct
3 Incorrect 27 ms 24188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Incorrect 23 ms 23928 KB Output isn't correct
3 Halted 0 ms 0 KB -