oj.uz

Submission #130514

# Submission time Handle Problem Language Result Execution time Memory
130514 2019-07-15T12:55:19 Z Bodo171 Mergers (JOI19_mergers) C++14
0 / 100
 255 ms 57624 KB 
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
using namespace std;
const int nmax=500005;
map<int,int> ap[nmax];
vector<int> v[nmax];
int l[nmax],r[nmax],p[nmax],closed[nmax],w[nmax],sons[nmax],rele[nmax],tot[nmax],col[nmax],c[nmax],tt[nmax];
int nr,n,i,paths,k,x,y,frz;
void baga(int path,int cc)
{
    ap[path][cc]++;
    if(ap[path][cc]==1) rele[path]++;
    if(ap[path][cc]==tot[cc]) rele[path]--;
}
void dfs(int x)
{
    int big=0;
    w[x]=1;
    ++nr;l[x]=nr;col[nr]=c[x];
    for(int i=0;i<v[x].size();i++)
        if(!w[v[x][i]])
    {
        tt[v[x][i]]=x;
        dfs(v[x][i]);
        if(w[v[x][i]]>w[big])
            big=v[x][i];
        w[x]+=w[v[x][i]];
    }
    if(big&&(!closed[big])) p[x]=p[big];
    else
    {
        p[x]=++paths;
        if(big) sons[paths]++;
    }
    baga(p[x],c[x]);
    for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=big&&v[x][i]!=tt[x])
    {
        if(closed[v[x][i]]) sons[p[x]]++;
        else
        {
            for(int j=l[v[x][i]];j<=r[v[x][i]];j++)
                baga(p[x],col[j]);
        }
    }
    if(rele[p[x]]==0)
    {
        closed[x]=1;
        if(sons[p[x]]==0) frz++;
    }
    r[x]=nr;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(i=1;i<=n-1;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        cin>>c[i];
        tot[c[i]]++;
    }
    dfs(1);
    if(sons[p[1]]==1) frz++;
    if(frz==1) frz=0;
    cout<<(frz+1)/2;
    return 0;
}

Compilation message

mergers.cpp: In function 'void dfs(int)':
mergers.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
mergers.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35704 KB Output is correct
2 Correct 34 ms 35704 KB Output is correct
3 Correct 34 ms 35704 KB Output is correct
4 Correct 34 ms 35704 KB Output is correct
5 Correct 35 ms 35580 KB Output is correct
6 Correct 42 ms 35608 KB Output is correct
7 Correct 36 ms 35704 KB Output is correct
8 Correct 35 ms 35576 KB Output is correct
9 Correct 34 ms 35704 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct
11 Correct 34 ms 35704 KB Output is correct
12 Correct 34 ms 35576 KB Output is correct
13 Correct 34 ms 35580 KB Output is correct
14 Correct 43 ms 35576 KB Output is correct
15 Incorrect 35 ms 35704 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35704 KB Output is correct
2 Correct 34 ms 35704 KB Output is correct
3 Correct 34 ms 35704 KB Output is correct
4 Correct 34 ms 35704 KB Output is correct
5 Correct 35 ms 35580 KB Output is correct
6 Correct 42 ms 35608 KB Output is correct
7 Correct 36 ms 35704 KB Output is correct
8 Correct 35 ms 35576 KB Output is correct
9 Correct 34 ms 35704 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct
11 Correct 34 ms 35704 KB Output is correct
12 Correct 34 ms 35576 KB Output is correct
13 Correct 34 ms 35580 KB Output is correct
14 Correct 43 ms 35576 KB Output is correct
15 Incorrect 35 ms 35704 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35704 KB Output is correct
2 Correct 34 ms 35704 KB Output is correct
3 Correct 34 ms 35704 KB Output is correct
4 Correct 34 ms 35704 KB Output is correct
5 Correct 35 ms 35580 KB Output is correct
6 Correct 42 ms 35608 KB Output is correct
7 Correct 36 ms 35704 KB Output is correct
8 Correct 35 ms 35576 KB Output is correct
9 Correct 34 ms 35704 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct
11 Correct 34 ms 35704 KB Output is correct
12 Correct 34 ms 35576 KB Output is correct
13 Correct 34 ms 35580 KB Output is correct
14 Correct 43 ms 35576 KB Output is correct
15 Incorrect 35 ms 35704 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 47044 KB Output is correct
2 Correct 122 ms 47892 KB Output is correct
3 Correct 38 ms 36060 KB Output is correct
4 Correct 36 ms 35872 KB Output is correct
5 Correct 34 ms 35676 KB Output is correct
6 Correct 34 ms 35704 KB Output is correct
7 Correct 37 ms 35996 KB Output is correct
8 Incorrect 255 ms 57624 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35704 KB Output is correct
2 Correct 34 ms 35704 KB Output is correct
3 Correct 34 ms 35704 KB Output is correct
4 Correct 34 ms 35704 KB Output is correct
5 Correct 35 ms 35580 KB Output is correct
6 Correct 42 ms 35608 KB Output is correct
7 Correct 36 ms 35704 KB Output is correct
8 Correct 35 ms 35576 KB Output is correct
9 Correct 34 ms 35704 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct
11 Correct 34 ms 35704 KB Output is correct
12 Correct 34 ms 35576 KB Output is correct
13 Correct 34 ms 35580 KB Output is correct
14 Correct 43 ms 35576 KB Output is correct
15 Incorrect 35 ms 35704 KB Output isn't correct
16 Halted 0 ms 0 KB -