oj.uz

Submission #1077071

# Submission time Handle Problem Language Result Execution time Memory
1077071 2024-08-26T22:19:04 Z guanex Simurgh (IOI17_simurgh) C++14
13 / 100
 70 ms 4700 KB 
#include "simurgh.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, int> ci;
typedef pair<string, int> si;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define inf INT_MAX/2
#define fro front

vi ans;
vector<vii> x(501);
ii fa[501];
int rs[125001];
int vis[501];
vi tree;
int z;
int cn = 0;

void df(int no, int f,int ideje){
    if(ideje != -1){
        tree.pb(ideje);
    }
    fa[no] = ii(f, ideje);
    vis[no] = 1;
    for(auto e:x[no]){
        if(vis[e.fi]){
            continue;
        }
        df(e.fi, no, e.se);
    }
}

void dfs(int no,int ideje){
    vis[no] = 1;
    //cout << "currently " << no << '\n';
    for(auto e:x[no]){
        if(e.se == ideje || vis[e.fi] == 2){
            continue;
        }
        if(vis[e.fi] == 1){
            //cout << ".."<< e.fi << endl;
            int f = no;
            while(f != e.fi){
                int ff = f;
                f = fa[f].fi;
                if(rs[fa[ff].se] != -1){
                    vi tre = tree;
                    for(int i = 0; i < tre.size(); ++i){
                        if(tre[i] == fa[ff].se){
                            tre[i] = e.se;
                        }
                    }
                    //cout << f << " " << ff << " " << fa[ff].se << endl;
                    for(auto e:tre){
                        //cout << e << " ";
                    }
                    //cout << endl;
                    int g = count_common_roads(tre);
                    cn++;
                    assert ( cn < 29999 );
                    //cout << g << endl;
                    if(g == z){
                        rs[e.se] = rs[fa[ff].se];
                    }else if(g == z+1){
                        rs[e.se] = 1;
                    }else{
                        rs[e.se] = 0;
                    }
                    f = e.fi;
                }
            }
            if(rs[e.se] == -1){
                f = no;
                vector < int > seen;
                while(f != e.fi){
                    int ff = f;
                    f = fa[f].fi;
                    vi tre = tree;
                    //cout << f << " " << ff << " " << fa[ff].se << endl;
                    for(int i = 0; i < tre.size(); ++i){
                        if(tre[i] == fa[ff].se){
                            tre[i] = e.se;
                        }
                    }
                    for(auto e:tre){
                        //cout << e << " ";
                    }
                    //cout << endl;
                    int g = count_common_roads(tre);
                    cn++;
                    assert ( cn < 29999 );
                    seen.push_back ( fa[ff].se );
                    //cout << g << endl;
                    if(g == z){
                        continue;
                    }else if(g == z+1){
                        rs[e.se] = 1;
                        rs[fa[ff].se] = 0;
                        f = e.fi;
                    }else{
                        rs[e.se] = 0;
                        rs[fa[ff].se] = 1;
                        f = e.fi;
                    }
                }
                if ( rs[e.se] == -1 ) {
                    rs[e.se] = 0;
                    for (auto &e : seen) rs[e] = 0;
                }
            }
            f = no;
            while(f != e.fi){
                int ff = f;
                f = fa[f].fi;
                if(rs[fa[ff].se] != -1){
                    continue;
                }
                vi tre = tree;
                for(int i = 0; i < tre.size(); ++i){
                    if(tre[i] == fa[ff].se){
                        tre[i] = e.se;
                    }
                }
                //cout << f << " " << ff << " " << fa[ff].se << endl;
                for(auto e:tre){
                    //cout << e << " ";
                }
                //cout << endl;
                int g = count_common_roads(tre);
                cn++;
                assert ( cn < 29999 );
                //cout << g << endl;
                if(g == z){
                    rs[fa[ff].se] = rs[e.se];
                }else if(g == z+1){
                    rs[e.se] = 1;
                    rs[fa[ff].se] = 0;
                    f = e.fi;
                }else{
                    rs[e.se] = 0;
                    rs[fa[ff].se] = 1;
                    f = e.fi;
                }
            }
            //cout << endl << endl;
            continue;
        }
        dfs(e.fi, e.se);
    }
    vis[no] = 2;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    for(int i = 0; i < u.size(); ++i){
        x[u[i]].pb(ii(v[i], i));
        x[v[i]].pb(ii(u[i], i));
    }
    fa[0] = ii(0, -1);
    df(0, 0, -1);
    memset(vis, 0, sizeof vis);
    memset(rs, -1, sizeof rs);
    z = count_common_roads(tree);
    if(z == n-1){
        return tree;
    }
    dfs(0, -1);
    ////cout << 1 << endl;
    for(auto e:tree){
        if(rs[e] == -1){
            rs[e] = 1;
        }
    }
    for(int i = 0; i < 125001; ++i){
        if(rs[i] == 1)
            ans.pb(i);
    }
    assert(ans.size() <= n - 1);
    for(auto e:ans){
        //cout << e << endl;
    }
	return ans;
}

Compilation message

simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:62:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                     for(int i = 0; i < tre.size(); ++i){
      |                                    ~~^~~~~~~~~~~~
simurgh.cpp:68:30: warning: unused variable 'e' [-Wunused-variable]
   68 |                     for(auto e:tre){
      |                              ^
simurgh.cpp:94:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                     for(int i = 0; i < tre.size(); ++i){
      |                                    ~~^~~~~~~~~~~~
simurgh.cpp:99:30: warning: unused variable 'e' [-Wunused-variable]
   99 |                     for(auto e:tre){
      |                              ^
simurgh.cpp:133:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |                 for(int i = 0; i < tre.size(); ++i){
      |                                ~~^~~~~~~~~~~~
simurgh.cpp:139:26: warning: unused variable 'e' [-Wunused-variable]
  139 |                 for(auto e:tre){
      |                          ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:168:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for(int i = 0; i < u.size(); ++i){
      |                    ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp:191:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  191 |     assert(ans.size() <= n - 1);
      |            ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:192:14: warning: unused variable 'e' [-Wunused-variable]
  192 |     for(auto e:ans){
      |              ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB correct
2 Correct 0 ms 860 KB correct
3 Correct 1 ms 860 KB correct
4 Correct 1 ms 860 KB correct
5 Correct 0 ms 860 KB correct
6 Correct 0 ms 860 KB correct
7 Correct 1 ms 860 KB correct
8 Correct 1 ms 856 KB correct
9 Correct 1 ms 856 KB correct
10 Correct 1 ms 860 KB correct
11 Correct 0 ms 716 KB correct
12 Correct 1 ms 856 KB correct
13 Correct 1 ms 860 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB correct
2 Correct 0 ms 860 KB correct
3 Correct 1 ms 860 KB correct
4 Correct 1 ms 860 KB correct
5 Correct 0 ms 860 KB correct
6 Correct 0 ms 860 KB correct
7 Correct 1 ms 860 KB correct
8 Correct 1 ms 856 KB correct
9 Correct 1 ms 856 KB correct
10 Correct 1 ms 860 KB correct
11 Correct 0 ms 716 KB correct
12 Correct 1 ms 856 KB correct
13 Correct 1 ms 860 KB correct
14 Correct 2 ms 860 KB correct
15 Correct 2 ms 860 KB correct
16 Correct 2 ms 1012 KB correct
17 Correct 1 ms 976 KB correct
18 Correct 1 ms 860 KB correct
19 Correct 2 ms 976 KB correct
20 Correct 1 ms 980 KB correct
21 Correct 1 ms 860 KB correct
22 Correct 1 ms 860 KB correct
23 Correct 1 ms 860 KB correct
24 Correct 1 ms 856 KB correct
25 Correct 1 ms 860 KB correct
26 Correct 1 ms 860 KB correct
27 Correct 2 ms 860 KB correct
28 Runtime error 3 ms 1488 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB correct
2 Correct 0 ms 860 KB correct
3 Correct 1 ms 860 KB correct
4 Correct 1 ms 860 KB correct
5 Correct 0 ms 860 KB correct
6 Correct 0 ms 860 KB correct
7 Correct 1 ms 860 KB correct
8 Correct 1 ms 856 KB correct
9 Correct 1 ms 856 KB correct
10 Correct 1 ms 860 KB correct
11 Correct 0 ms 716 KB correct
12 Correct 1 ms 856 KB correct
13 Correct 1 ms 860 KB correct
14 Correct 2 ms 860 KB correct
15 Correct 2 ms 860 KB correct
16 Correct 2 ms 1012 KB correct
17 Correct 1 ms 976 KB correct
18 Correct 1 ms 860 KB correct
19 Correct 2 ms 976 KB correct
20 Correct 1 ms 980 KB correct
21 Correct 1 ms 860 KB correct
22 Correct 1 ms 860 KB correct
23 Correct 1 ms 860 KB correct
24 Correct 1 ms 856 KB correct
25 Correct 1 ms 860 KB correct
26 Correct 1 ms 860 KB correct
27 Correct 2 ms 860 KB correct
28 Runtime error 3 ms 1488 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB correct
2 Correct 1 ms 860 KB correct
3 Incorrect 70 ms 4700 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 860 KB correct
2 Correct 0 ms 860 KB correct
3 Correct 1 ms 860 KB correct
4 Correct 1 ms 860 KB correct
5 Correct 0 ms 860 KB correct
6 Correct 0 ms 860 KB correct
7 Correct 1 ms 860 KB correct
8 Correct 1 ms 856 KB correct
9 Correct 1 ms 856 KB correct
10 Correct 1 ms 860 KB correct
11 Correct 0 ms 716 KB correct
12 Correct 1 ms 856 KB correct
13 Correct 1 ms 860 KB correct
14 Correct 2 ms 860 KB correct
15 Correct 2 ms 860 KB correct
16 Correct 2 ms 1012 KB correct
17 Correct 1 ms 976 KB correct
18 Correct 1 ms 860 KB correct
19 Correct 2 ms 976 KB correct
20 Correct 1 ms 980 KB correct
21 Correct 1 ms 860 KB correct
22 Correct 1 ms 860 KB correct
23 Correct 1 ms 860 KB correct
24 Correct 1 ms 856 KB correct
25 Correct 1 ms 860 KB correct
26 Correct 1 ms 860 KB correct
27 Correct 2 ms 860 KB correct
28 Runtime error 3 ms 1488 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -