Submission details
Task:Ice cream
Sender:OOliOO_slayer
Submission time:2016-09-20 17:05:28 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.08 sdetails
#20.07 sdetails
#30.11 sdetails
#40.11 sdetails
#50.06 sdetails
#60.07 sdetails
#70.06 sdetails
#80.12 sdetails
#90.11 sdetails
#100.07 sdetails
#110.08 sdetails
#120.08 sdetails
#130.14 sdetails
#140.19 sdetails
#150.08 sdetails
#160.09 sdetails
#170.09 sdetails
#180.14 sdetails
#190.19 sdetails
#200.17 sdetails

Code

#include <iostream>
#include <vector>
#include <set>

typedef long long LL;
using namespace std;

vector<bool> visited;
vector<int> colors;
vector<vector<int> > neighbors;

void dfs(int v, set<int>& colors_found, vector<int>& vertices_found){
    if(visited[v]) return;
    visited[v] = true;
    vertices_found.push_back(v);
    colors_found.insert(colors[v]);
    for(auto u : neighbors[v]){
        dfs(u, colors_found, vertices_found);
    }
}

int main(){
    int nVertices, nEdges;
    cin >> nVertices >> nEdges;
    for(int i = 0; i < nVertices; i++){
        int x; cin >> x; colors.push_back(x);
    }
    
    neighbors.resize(nVertices);
    for(int i = 0; i < nEdges; i++){
        int u,v; cin >> u >> v; u--; v--;
        neighbors[u].push_back(v);
        neighbors[v].push_back(u);
    }
    
    visited.resize(nVertices);
    vector<int> ans(nVertices);
    
    cout << "lol" << endl;
    
    for(int v = 0; v < nVertices; v++){
        if(visited[v]) continue;
        
        set<int> colors_found;
        vector<int> vertices_found;
        vector<int> found;
        dfs(v, colors_found, vertices_found);
        for(auto u : vertices_found){
            ans[u] = colors_found.size();
        }
    }
    
    for(int i = 0; i < nVertices; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}

Test details

Test 1

Verdict:

input
47623 1000
6085 3581 2784 1594 9991 7789 ...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
lol
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 2

Verdict:

input
29933 10000
37075 97477 24892 91827 86196 ...

correct output
2 6 1 1 5 1 1 7 9 2 2 2 1 1 3 ...

user output
lol
2 6 1 1 5 1 1 7 9 2 2 2 1 1 3 ...

Test 3

Verdict:

input
82771 50000
84 19 10 43 44 51 77 9 4 1 21 ...

correct output
2 1 1 1 100 1 1 1 100 100 1 1 ...

user output
lol
2 1 1 1 100 1 1 1 100 100 1 1 ...

Test 4

Verdict:

input
11645 100000
3041 8953 9167 1268 2312 5911 ...

correct output
6836 6836 6836 6836 6836 6836 ...

user output
lol
6836 6836 6836 6836 6836 6836 ...

Test 5

Verdict:

input
1041 100
43553 8035 14355 19335 24786 7...

correct output
2 1 1 3 1 1 1 2 1 1 1 1 3 1 1 ...

user output
lol
2 1 1 3 1 1 1 2 1 1 1 1 3 1 1 ...

Test 6

Verdict:

input
55898 1000
73 44 15 26 63 51 15 71 73 48 ...

correct output
1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 ...

user output
lol
1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 ...

Test 7

Verdict:

input
12027 10000
2456 845 5196 3813 3093 2331 2...

correct output
2 5542 5542 1 5542 5542 5542 5...

user output
lol
2 5542 5542 1 5542 5542 5542 5...

Test 8

Verdict:

input
55977 50000
79310 84043 72794 74090 312 15...

correct output
1 33498 33498 33498 33498 1 1 ...

user output
lol
1 33498 33498 33498 33498 1 1 ...

Test 9

Verdict:

input
16237 100000
57 43 3 66 59 10 24 41 56 23 5...

correct output
100 100 100 100 100 100 100 10...

user output
lol
100 100 100 100 100 100 100 10...

Test 10

Verdict:

input
93552 100
31 7952 1106 2779 1980 8776 56...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
lol
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 11

Verdict:

input
100000 1000
99793 93845 56091 42020 27225 ...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
lol
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 12

Verdict:

input
100000 10000
45 12 5 45 21 73 12 34 97 14 6...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
lol
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 13

Verdict:

input
100000 50000
3967 8608 4873 6065 3304 1388 ...

correct output
27 10 2 1 205 2 1 5 752 9 2 26...

user output
lol
27 10 2 1 205 2 1 5 752 9 2 26...

Test 14

Verdict:

input
70000 100000
9570 57890 88434 83611 76325 3...

correct output
1 1 1 47966 47966 47966 47966 ...

user output
lol
1 1 1 47966 47966 47966 47966 ...

Test 15

Verdict:

input
100000 100
84 34 32 36 64 83 29 4 36 57 9...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
lol
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 16

Verdict:

input
100000 1000
7080 7863 895 4001 3806 8637 7...

correct output
1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
lol
1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 17

Verdict:

input
100000 10000
13821 30085 25414 18462 40885 ...

correct output
1 1 3 1 1 2 1 1 1 2 1 1 1 1 1 ...

user output
lol
1 1 3 1 1 2 1 1 1 2 1 1 1 1 1 ...

Test 18

Verdict:

input
100000 50000
41 89 12 33 73 79 38 48 90 68 ...

correct output
4 1 21 1 2 2 1 1 3 2 3 7 6 20 ...

user output
lol
4 1 21 1 2 2 1 1 3 2 3 7 6 20 ...

Test 19

Verdict:

input
100000 100000
4325 2304 2625 9099 4244 1618 ...

correct output
9994 5 9994 9994 9994 1 9994 9...

user output
lol
9994 5 9994 9994 9994 1 9994 9...

Test 20

Verdict:

input
100000 100
68725 58766 50437 78768 4415 2...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
lol
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...