oj.uz

Submission #892303

# Submission time Handle Problem Language Result Execution time Memory
892303 2023-12-25T07:03:44 Z abcvuitunggio Simurgh (IOI17_simurgh) C++17
51 / 100
 513 ms 8672 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
    int u,v;
}e[150000];
int n,m,ch[150000],p[150000],used[150000],tin[501],tout[501],t,par[501],cur;
vector <int> ke[150000],ve;
set <int> s;
int ask(set <int> s){
    vector <int> r;
    for (int i:s)
        r.push_back(i);
    return count_common_roads(r);
}
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
bool unite(int i, int j){
    i=f(i);
    j=f(j);
    if (i==j)
        return false;
    p[j]=i;
    return true;
}
bool create_random_spanning_tree(){
    iota(p,p+n+1,0);
    for (int i=0;i<n;i++)
        ke[i].clear();
    s.clear();
    for (int i=0;i<m;i++)
        if (ch[i]==1){
            used[i]=unite(e[i].u,e[i].v);
            if (used[i]){
                ke[e[i].u].push_back(i);
                ke[e[i].v].push_back(i);
                s.insert(i);
            }
        }
    if (s.size()==n-1)
        return false;
    for (int i=0;i<m;i++)
        if (ch[i]==-1){
            used[i]=unite(e[i].u,e[i].v);
            if (used[i]){
                ke[e[i].u].push_back(i);
                ke[e[i].v].push_back(i);
                s.insert(i);
            }
        }
    cur=ask(s);
    return true;
}
void dfs(int u, int parent){
    tin[u]=++t;
    for (int i:ke[u]){
        int v=e[i].u^e[i].v^u;
        if (v!=parent){
            par[v]=i;
            dfs(v,u);
        }
    }
    tout[u]=t;
}
bool isancestor(int u, int v){
    return (tin[u]<=tin[v]&&tout[u]>=tout[v]);
}
void get_path(int u, int v){
    ve.clear();
    while (!isancestor(u,v)){
        ve.push_back(par[u]);
        u^=e[par[u]].u^e[par[u]].v;
    }
    while (!isancestor(v,u)){
        ve.push_back(par[v]);
        v^=e[par[v]].u^e[par[v]].v;
    }
}
vector <int> find_roads(int N, vector <int> u, vector <int> v){
    n=N,m=u.size();
    for (int i=0;i<m;i++)
        e[i]={u[i],v[i]};
    fill(ch,ch+m,-1);
    while (create_random_spanning_tree()){
        t=0;
        dfs(0,0);
        int restart=0;
        for (int i=0;i<m;i++)
            if (!used[i]&&ch[i]==-1){
                get_path(u[i],v[i]);
                for (int j:ve){
                    if (ch[j]==1){
                        s.erase(j);
                        s.insert(i);
                        ch[i]=1-cur+ask(s);
                        s.erase(i);
                        s.insert(j);
                        break;
                    }
                }
                if (ch[i]==0)
                    continue;
                if (ch[i]==1){
                    restart=1;
                    break;
                }
                int mx=-1;
                for (int j:ve){
                    s.erase(j);
                    s.insert(i);
                    ch[j]=ask(s)-cur;
                    mx=max(mx,ch[j]);
                    s.erase(i);
                    s.insert(j);
                }
                if (mx==1){
                    ch[i]=1;
                    restart=1;
                    for (int j:ve)
                        ch[j]^=1;
                    break;
                }
                ch[i]=0;
                for (int j:ve)
                    ch[j]=-ch[j];
                restart=1;
                break;
            }
        if (!restart)
            break;
    }
    vector <int> res;
    for (int i:s)
        res.push_back(i);
    return res;
}

Compilation message

simurgh.cpp: In function 'bool create_random_spanning_tree()':
simurgh.cpp:41:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     if (s.size()==n-1)
      |         ~~~~~~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6760 KB correct
2 Correct 1 ms 6748 KB correct
3 Correct 1 ms 6748 KB correct
4 Correct 1 ms 6748 KB correct
5 Correct 1 ms 6748 KB correct
6 Correct 1 ms 6744 KB correct
7 Correct 1 ms 6748 KB correct
8 Correct 1 ms 6744 KB correct
9 Correct 1 ms 6748 KB correct
10 Correct 1 ms 6744 KB correct
11 Correct 2 ms 6748 KB correct
12 Correct 1 ms 6748 KB correct
13 Correct 1 ms 6748 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6760 KB correct
2 Correct 1 ms 6748 KB correct
3 Correct 1 ms 6748 KB correct
4 Correct 1 ms 6748 KB correct
5 Correct 1 ms 6748 KB correct
6 Correct 1 ms 6744 KB correct
7 Correct 1 ms 6748 KB correct
8 Correct 1 ms 6744 KB correct
9 Correct 1 ms 6748 KB correct
10 Correct 1 ms 6744 KB correct
11 Correct 2 ms 6748 KB correct
12 Correct 1 ms 6748 KB correct
13 Correct 1 ms 6748 KB correct
14 Correct 6 ms 7000 KB correct
15 Correct 5 ms 6744 KB correct
16 Correct 5 ms 6748 KB correct
17 Correct 5 ms 6544 KB correct
18 Correct 3 ms 6748 KB correct
19 Correct 4 ms 6772 KB correct
20 Correct 4 ms 6744 KB correct
21 Correct 4 ms 6748 KB correct
22 Correct 4 ms 6748 KB correct
23 Correct 4 ms 6900 KB correct
24 Correct 4 ms 6748 KB correct
25 Correct 1 ms 6744 KB correct
26 Correct 3 ms 6744 KB correct
27 Correct 3 ms 6744 KB correct
28 Correct 3 ms 6748 KB correct
29 Correct 2 ms 6760 KB correct
30 Correct 3 ms 6744 KB correct
31 Correct 4 ms 6748 KB correct
32 Correct 3 ms 6748 KB correct
33 Correct 3 ms 6748 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6760 KB correct
2 Correct 1 ms 6748 KB correct
3 Correct 1 ms 6748 KB correct
4 Correct 1 ms 6748 KB correct
5 Correct 1 ms 6748 KB correct
6 Correct 1 ms 6744 KB correct
7 Correct 1 ms 6748 KB correct
8 Correct 1 ms 6744 KB correct
9 Correct 1 ms 6748 KB correct
10 Correct 1 ms 6744 KB correct
11 Correct 2 ms 6748 KB correct
12 Correct 1 ms 6748 KB correct
13 Correct 1 ms 6748 KB correct
14 Correct 6 ms 7000 KB correct
15 Correct 5 ms 6744 KB correct
16 Correct 5 ms 6748 KB correct
17 Correct 5 ms 6544 KB correct
18 Correct 3 ms 6748 KB correct
19 Correct 4 ms 6772 KB correct
20 Correct 4 ms 6744 KB correct
21 Correct 4 ms 6748 KB correct
22 Correct 4 ms 6748 KB correct
23 Correct 4 ms 6900 KB correct
24 Correct 4 ms 6748 KB correct
25 Correct 1 ms 6744 KB correct
26 Correct 3 ms 6744 KB correct
27 Correct 3 ms 6744 KB correct
28 Correct 3 ms 6748 KB correct
29 Correct 2 ms 6760 KB correct
30 Correct 3 ms 6744 KB correct
31 Correct 4 ms 6748 KB correct
32 Correct 3 ms 6748 KB correct
33 Correct 3 ms 6748 KB correct
34 Correct 370 ms 7424 KB correct
35 Correct 371 ms 7256 KB correct
36 Correct 261 ms 7000 KB correct
37 Correct 19 ms 6748 KB correct
38 Correct 361 ms 7432 KB correct
39 Correct 321 ms 7328 KB correct
40 Correct 233 ms 7212 KB correct
41 Correct 357 ms 7260 KB correct
42 Correct 364 ms 7436 KB correct
43 Correct 131 ms 7004 KB correct
44 Correct 106 ms 7048 KB correct
45 Correct 123 ms 7000 KB correct
46 Correct 101 ms 7008 KB correct
47 Correct 43 ms 6880 KB correct
48 Correct 6 ms 6744 KB correct
49 Correct 15 ms 6748 KB correct
50 Correct 42 ms 6880 KB correct
51 Correct 145 ms 7096 KB correct
52 Correct 108 ms 7000 KB correct
53 Correct 95 ms 7000 KB correct
54 Correct 132 ms 7112 KB correct
55 Correct 128 ms 7236 KB correct
56 Correct 117 ms 7000 KB correct
57 Correct 119 ms 7000 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB correct
2 Correct 1 ms 6748 KB correct
3 Incorrect 513 ms 8672 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6760 KB correct
2 Correct 1 ms 6748 KB correct
3 Correct 1 ms 6748 KB correct
4 Correct 1 ms 6748 KB correct
5 Correct 1 ms 6748 KB correct
6 Correct 1 ms 6744 KB correct
7 Correct 1 ms 6748 KB correct
8 Correct 1 ms 6744 KB correct
9 Correct 1 ms 6748 KB correct
10 Correct 1 ms 6744 KB correct
11 Correct 2 ms 6748 KB correct
12 Correct 1 ms 6748 KB correct
13 Correct 1 ms 6748 KB correct
14 Correct 6 ms 7000 KB correct
15 Correct 5 ms 6744 KB correct
16 Correct 5 ms 6748 KB correct
17 Correct 5 ms 6544 KB correct
18 Correct 3 ms 6748 KB correct
19 Correct 4 ms 6772 KB correct
20 Correct 4 ms 6744 KB correct
21 Correct 4 ms 6748 KB correct
22 Correct 4 ms 6748 KB correct
23 Correct 4 ms 6900 KB correct
24 Correct 4 ms 6748 KB correct
25 Correct 1 ms 6744 KB correct
26 Correct 3 ms 6744 KB correct
27 Correct 3 ms 6744 KB correct
28 Correct 3 ms 6748 KB correct
29 Correct 2 ms 6760 KB correct
30 Correct 3 ms 6744 KB correct
31 Correct 4 ms 6748 KB correct
32 Correct 3 ms 6748 KB correct
33 Correct 3 ms 6748 KB correct
34 Correct 370 ms 7424 KB correct
35 Correct 371 ms 7256 KB correct
36 Correct 261 ms 7000 KB correct
37 Correct 19 ms 6748 KB correct
38 Correct 361 ms 7432 KB correct
39 Correct 321 ms 7328 KB correct
40 Correct 233 ms 7212 KB correct
41 Correct 357 ms 7260 KB correct
42 Correct 364 ms 7436 KB correct
43 Correct 131 ms 7004 KB correct
44 Correct 106 ms 7048 KB correct
45 Correct 123 ms 7000 KB correct
46 Correct 101 ms 7008 KB correct
47 Correct 43 ms 6880 KB correct
48 Correct 6 ms 6744 KB correct
49 Correct 15 ms 6748 KB correct
50 Correct 42 ms 6880 KB correct
51 Correct 145 ms 7096 KB correct
52 Correct 108 ms 7000 KB correct
53 Correct 95 ms 7000 KB correct
54 Correct 132 ms 7112 KB correct
55 Correct 128 ms 7236 KB correct
56 Correct 117 ms 7000 KB correct
57 Correct 119 ms 7000 KB correct
58 Correct 1 ms 7000 KB correct
59 Correct 1 ms 6748 KB correct
60 Incorrect 513 ms 8672 KB WA in grader: NO
61 Halted 0 ms 0 KB -