oj.uz

Submission #359251

# Submission time Handle Problem Language Result Execution time Memory
359251 2021-01-26T14:07:41 Z beksultan04 Simurgh (IOI17_simurgh) C++14
30 / 100
 3000 ms 6620 KB 
#include "simurgh.h"
#ifndef EVAL
#include "grader.cpp"
#endif // EVAL
#include <bits/stdc++.h>
using namespace std;
#define lol long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define eps 1e-12
vector <pii> g[501];
vector <int> which,cycle,top,otvet;
bool vis[501],can[1000001],used[1000001];
int pos[1000001];
int kto[501][501];
void dfs(int x){
    vis[x] = 1;
    for (pii to: g[x])
        if (vis[to.fr] == 0){
            which.pb(to.sc);
            dfs(to.fr);
        }
}

void find_cycle(int x,int pr = -1){
    top.pb(x);
    vis[x]=1;
    for (pii to: g[x]){
        if (to.fr != pr && can[to.sc] == 1){
            if (vis[to.fr] == 1){
                int pr = to.fr;
                while (!top.empty()){
                    cycle.pb(kto[top.back()][pr]);
                    pr = top.back();
                    if (top.back() == to.fr)break;
                    top.pop_back();
                }
                ret;
            }
            if (!cycle.empty())ret;
            if (vis[to.fr] == 0){
                find_cycle(to.fr,x);
            }
        }
            if (!cycle.empty())ret;
    }
            if (!cycle.empty())ret;
    top.pop_back();
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	vector<int> bosh,a;
	int i;
	for (i=0;i<u.size();++i){
        pos[i] = -1;
        g[u[i]].pb({v[i],i});
	    g[v[i]].pb({u[i],i});
	    kto[u[i]][v[i]] = i;
	    kto[v[i]][u[i]] = i;
        a.pb(0);
        otvet.pb(-1);
	}
	dfs(0);
	for (int x : which){
        used[x] = 1;
        can[x] = 1;
        a[x] = 1;
        otvet[x]=1;
	}

	for (i=0;i<u.size();++i)
        if (!used[i])
            bosh.pb(i);

    for (int x: bosh){
        for (i=0;i<n;++i)vis[i] = 0;
        can[x] = 1;
        a[x] = 1;
        cycle.clear();
        top.clear();
        vector <pii> ans;
        find_cycle(0);
        int mx = -1;
        for (int y: cycle){
            if (pos[y] != -1 && mx == -1){
                if (otvet[y] == 0){
                    a[y]=0;
                    vector <int> ask;
                    for (i=0;i<u.size();++i)
                        if (a[i] == 1)ask.pb(i);
                    int xxx = count_common_roads(ask);
                    mx = xxx;
                    a[y]=1;
                }
                else {
                    a[y]=0;
                    vector <int> ask;
                    for (i=0;i<u.size();++i)
                        if (a[i] == 1)ask.pb(i);
                    int xxx = count_common_roads(ask);
                    mx = xxx+1;
                    a[y]=1;

                }
                continue;
            }
            else if (pos[y] == -1){

                a[y]=0;
                vector <int> ask;
                for (i=0;i<u.size();++i)
                    if (a[i] == 1)ask.pb(i);
                int xxx = count_common_roads(ask);
                ans.pb({xxx,y});
                a[y]=1;
            }
        }
        sort(all(ans));
        if (ans.empty())continue;
        if (mx == -1)
            mx = ans.back().fr;
        for (i=0;i<ans.size();++i){
            if (mx > ans[i].fr){
                pos[ans[i].sc] = 1;
                otvet[ans[i].sc]=1;
            }
            else
                otvet[ans[i].sc]=0;
        }
        can[x]=0;
        a[x]=0;
    }
    vector <int> res;
    for (i =0;i<otvet.size();++i){
        if (otvet[i] == 1){
            res.pb(i);
        }
    }
    ret res;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:70:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (i=0;i<u.size();++i){
      |           ~^~~~~~~~~
simurgh.cpp:87:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for (i=0;i<u.size();++i)
      |           ~^~~~~~~~~
simurgh.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |                     for (i=0;i<u.size();++i)
      |                              ~^~~~~~~~~
simurgh.cpp:114:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                     for (i=0;i<u.size();++i)
      |                              ~^~~~~~~~~
simurgh.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |                 for (i=0;i<u.size();++i)
      |                          ~^~~~~~~~~
simurgh.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for (i=0;i<ans.size();++i){
      |                  ~^~~~~~~~~~~
simurgh.cpp:150:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (i =0;i<otvet.size();++i){
      |               ~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 117 ms 620 KB correct
15 Correct 115 ms 492 KB correct
16 Correct 119 ms 748 KB correct
17 Correct 78 ms 492 KB correct
18 Correct 15 ms 620 KB correct
19 Correct 83 ms 492 KB correct
20 Correct 75 ms 584 KB correct
21 Correct 67 ms 492 KB correct
22 Correct 17 ms 492 KB correct
23 Correct 14 ms 492 KB correct
24 Correct 11 ms 492 KB correct
25 Correct 1 ms 492 KB correct
26 Correct 11 ms 492 KB correct
27 Correct 12 ms 492 KB correct
28 Correct 3 ms 492 KB correct
29 Correct 1 ms 492 KB correct
30 Correct 15 ms 492 KB correct
31 Correct 16 ms 492 KB correct
32 Correct 14 ms 492 KB correct
33 Correct 15 ms 620 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 117 ms 620 KB correct
15 Correct 115 ms 492 KB correct
16 Correct 119 ms 748 KB correct
17 Correct 78 ms 492 KB correct
18 Correct 15 ms 620 KB correct
19 Correct 83 ms 492 KB correct
20 Correct 75 ms 584 KB correct
21 Correct 67 ms 492 KB correct
22 Correct 17 ms 492 KB correct
23 Correct 14 ms 492 KB correct
24 Correct 11 ms 492 KB correct
25 Correct 1 ms 492 KB correct
26 Correct 11 ms 492 KB correct
27 Correct 12 ms 492 KB correct
28 Correct 3 ms 492 KB correct
29 Correct 1 ms 492 KB correct
30 Correct 15 ms 492 KB correct
31 Correct 16 ms 492 KB correct
32 Correct 14 ms 492 KB correct
33 Correct 15 ms 620 KB correct
34 Incorrect 2801 ms 2796 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Execution timed out 3063 ms 6620 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 117 ms 620 KB correct
15 Correct 115 ms 492 KB correct
16 Correct 119 ms 748 KB correct
17 Correct 78 ms 492 KB correct
18 Correct 15 ms 620 KB correct
19 Correct 83 ms 492 KB correct
20 Correct 75 ms 584 KB correct
21 Correct 67 ms 492 KB correct
22 Correct 17 ms 492 KB correct
23 Correct 14 ms 492 KB correct
24 Correct 11 ms 492 KB correct
25 Correct 1 ms 492 KB correct
26 Correct 11 ms 492 KB correct
27 Correct 12 ms 492 KB correct
28 Correct 3 ms 492 KB correct
29 Correct 1 ms 492 KB correct
30 Correct 15 ms 492 KB correct
31 Correct 16 ms 492 KB correct
32 Correct 14 ms 492 KB correct
33 Correct 15 ms 620 KB correct
34 Incorrect 2801 ms 2796 KB WA in grader: NO
35 Halted 0 ms 0 KB -