oj.uz

Submission #878590

# Submission time Handle Problem Language Result Execution time Memory
878590 2023-11-24T20:34:19 Z MasterTaster Paths (BOI18_paths) C++14
100 / 100
 568 ms 194436 KB 
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 300010
#define MAXK 8

using namespace std;

int n, m, k, a[MAXN];
ll cnt[MAXN][MAXK], ress, cntt[MAXN][MAXK][MAXK];
vector<pii> grane;
vector<int> g[MAXN];

int main() {
    cin>>n>>m>>k;

    for (int i=1; i<=n; i++)
        cin>>a[i];

    for (int i=0; i<m; i++)
    {
        int u, v; cin>>u>>v;
        grane.pb({u, v});
        g[u].pb(v); g[v].pb(u);
        cnt[u][a[v]]++;
        cnt[v][a[u]]++;
    }

    for (auto par:grane)
    {
        int u=par.xx, v=par.yy;
        if (a[u]==a[v]) continue;
        ress+=2;
        vector<int> boje;
        for (int i=1; i<=5; i++) if (a[u]!=i && a[v]!=i) boje.pb(i);
        int c1, c2, c3;
        c1=boje[0]; c2=boje[1]; c3=boje[2];
        ress+=2*((cnt[u][c1]*cnt[v][c2])+(cnt[u][c2]*cnt[v][c1]) + (cnt[u][c1]*cnt[v][c3])+(cnt[u][c3]*cnt[v][c1]) + (cnt[u][c3]*cnt[v][c2])+(cnt[u][c2]*cnt[v][c3]))
                +cnt[u][c1]+cnt[u][c2]+cnt[u][c3]+cnt[v][c1]+cnt[v][c2]+cnt[v][c3];
        //cout<<u<<" "<<v<<" "<<ress<<endl;
    }

    for (int u=1; u<=n; u++)
    {
        for (auto v:g[u])
        {
            if (a[u]==a[v]) continue;
            vector<int> boje;
            for (int i=1; i<=5; i++)
                if (a[u]!=i && a[v]!=i) boje.pb(i);
            for (auto c:boje)
                cntt[u][a[v]][c]+=cnt[v][c];
        }
    }

    //cout<<ress<<endl;
    ll press=0;
    for (int u=1; u<=n; u++)
    {
        vector<int> boje;
        for (int i=1; i<=5; i++) if (a[u]!=i) boje.pb(i);

        for (int i=0; i<boje.size(); i++)
        {
            for (int j=0; j<boje.size(); j++)
            {
                if (i==j) continue;
                int c1=boje[i], c2=boje[j], c3=-1, c4=-1;
                for (int k=0; k<boje.size(); k++) { if (k!=i && k!=j) { if (c3==-1) c3=boje[k]; else c4=boje[k]; } }
                press+=(cntt[u][c1][c2]*cntt[u][c3][c4]+cntt[u][c1][c2]*cntt[u][c4][c3]);
                //cout<<u<<" "<<" "<<c1<<" "<<c2<<" "<<c3<<" "<<c4<<": "<<press<<endl;

            }
        }
    }
    if (press%2==1) assert(0);
    //press/=2;
    ress+=press;
    //cout<<press<<endl;
    cout<<ress;
}
/*
8 7 5
1 2 3 1 4 5 5 4
1 2
2 3
3 4
2 5
5 6
2 7
7 8
 */

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:67:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (int i=0; i<boje.size(); i++)
      |                       ~^~~~~~~~~~~~
paths.cpp:69:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int j=0; j<boje.size(); j++)
      |                           ~^~~~~~~~~~~~
paths.cpp:73:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 for (int k=0; k<boje.size(); k++) { if (k!=i && k!=j) { if (c3==-1) c3=boje[k]; else c4=boje[k]; } }
      |                               ~^~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12908 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 20936 KB Output is correct
2 Correct 154 ms 24248 KB Output is correct
3 Correct 532 ms 192896 KB Output is correct
4 Correct 209 ms 39396 KB Output is correct
5 Correct 145 ms 27584 KB Output is correct
6 Correct 386 ms 138296 KB Output is correct
7 Correct 507 ms 192980 KB Output is correct
8 Correct 517 ms 194192 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12908 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 164 ms 20936 KB Output is correct
12 Correct 154 ms 24248 KB Output is correct
13 Correct 532 ms 192896 KB Output is correct
14 Correct 209 ms 39396 KB Output is correct
15 Correct 145 ms 27584 KB Output is correct
16 Correct 386 ms 138296 KB Output is correct
17 Correct 507 ms 192980 KB Output is correct
18 Correct 517 ms 194192 KB Output is correct
19 Correct 164 ms 24656 KB Output is correct
20 Correct 154 ms 23996 KB Output is correct
21 Correct 497 ms 193656 KB Output is correct
22 Correct 202 ms 39096 KB Output is correct
23 Correct 146 ms 27024 KB Output is correct
24 Correct 441 ms 138916 KB Output is correct
25 Correct 543 ms 193676 KB Output is correct
26 Correct 525 ms 194436 KB Output is correct
27 Correct 155 ms 22808 KB Output is correct
28 Correct 185 ms 26276 KB Output is correct
29 Correct 568 ms 193204 KB Output is correct
30 Correct 404 ms 108980 KB Output is correct
31 Correct 434 ms 109724 KB Output is correct
32 Correct 527 ms 190680 KB Output is correct
33 Correct 2 ms 12892 KB Output is correct
34 Correct 2 ms 12892 KB Output is correct
35 Correct 2 ms 12892 KB Output is correct
36 Correct 2 ms 12892 KB Output is correct
37 Correct 2 ms 12888 KB Output is correct
38 Correct 3 ms 12892 KB Output is correct
39 Correct 2 ms 12892 KB Output is correct
40 Correct 3 ms 12892 KB Output is correct
41 Correct 3 ms 12888 KB Output is correct
42 Correct 2 ms 12892 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 53 ms 15572 KB Output is correct
3 Correct 49 ms 15736 KB Output is correct
4 Correct 145 ms 72540 KB Output is correct
5 Correct 122 ms 73928 KB Output is correct
6 Correct 132 ms 73240 KB Output is correct
7 Correct 51 ms 15564 KB Output is correct
8 Correct 161 ms 73492 KB Output is correct
9 Correct 122 ms 73948 KB Output is correct
10 Correct 138 ms 73828 KB Output is correct
11 Correct 94 ms 45252 KB Output is correct
12 Correct 115 ms 58732 KB Output is correct
13 Correct 101 ms 45512 KB Output is correct
14 Correct 146 ms 73160 KB Output is correct
15 Correct 185 ms 73104 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 2 ms 12892 KB Output is correct
18 Correct 2 ms 12892 KB Output is correct
19 Correct 3 ms 12940 KB Output is correct
20 Correct 2 ms 12892 KB Output is correct
21 Correct 2 ms 12928 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 2 ms 12892 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 2 ms 12892 KB Output is correct