oj.uz

Submission #359236

# Submission time Handle Problem Language Result Execution time Memory
359236 2021-01-26T13:09:20 Z beksultan04 Simurgh (IOI17_simurgh) C++14
30 / 100
 3000 ms 6236 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 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){
        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);
        for (int y: cycle){
            a[y]=0;
            vector <int> ask;
            for (i=0;i<u.size();++i)
                if (a[i] == 1)ask.pb(i);
            ans.pb({count_common_roads(ask),y});
            a[y]=1;
        }
        sort(all(ans));
        int mn = ans.back().fr;
        for (i=0;i<ans.size();++i){
            if (mn > ans[i].fr)
                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:69:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (i=0;i<u.size();++i){
      |           ~^~~~~~~~~
simurgh.cpp:85:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (i=0;i<u.size();++i)
      |           ~^~~~~~~~~
simurgh.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for (i=0;i<u.size();++i)
      |                      ~^~~~~~~~~
simurgh.cpp:106: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]
  106 |         for (i=0;i<ans.size();++i){
      |                  ~^~~~~~~~~~~
simurgh.cpp:116:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     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 384 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 364 KB correct
13 Correct 1 ms 364 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 384 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 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 118 ms 492 KB correct
15 Correct 118 ms 620 KB correct
16 Correct 118 ms 492 KB correct
17 Correct 85 ms 512 KB correct
18 Correct 21 ms 492 KB correct
19 Correct 98 ms 492 KB correct
20 Correct 78 ms 492 KB correct
21 Correct 68 ms 492 KB correct
22 Correct 32 ms 620 KB correct
23 Correct 23 ms 620 KB correct
24 Correct 20 ms 492 KB correct
25 Correct 1 ms 512 KB correct
26 Correct 21 ms 492 KB correct
27 Correct 24 ms 492 KB correct
28 Correct 4 ms 492 KB correct
29 Correct 2 ms 492 KB correct
30 Correct 40 ms 492 KB correct
31 Correct 38 ms 492 KB correct
32 Correct 44 ms 492 KB correct
33 Correct 38 ms 492 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 384 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 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 118 ms 492 KB correct
15 Correct 118 ms 620 KB correct
16 Correct 118 ms 492 KB correct
17 Correct 85 ms 512 KB correct
18 Correct 21 ms 492 KB correct
19 Correct 98 ms 492 KB correct
20 Correct 78 ms 492 KB correct
21 Correct 68 ms 492 KB correct
22 Correct 32 ms 620 KB correct
23 Correct 23 ms 620 KB correct
24 Correct 20 ms 492 KB correct
25 Correct 1 ms 512 KB correct
26 Correct 21 ms 492 KB correct
27 Correct 24 ms 492 KB correct
28 Correct 4 ms 492 KB correct
29 Correct 2 ms 492 KB correct
30 Correct 40 ms 492 KB correct
31 Correct 38 ms 492 KB correct
32 Correct 44 ms 492 KB correct
33 Correct 38 ms 492 KB correct
34 Incorrect 2814 ms 2668 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 3060 ms 6236 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 384 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 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 118 ms 492 KB correct
15 Correct 118 ms 620 KB correct
16 Correct 118 ms 492 KB correct
17 Correct 85 ms 512 KB correct
18 Correct 21 ms 492 KB correct
19 Correct 98 ms 492 KB correct
20 Correct 78 ms 492 KB correct
21 Correct 68 ms 492 KB correct
22 Correct 32 ms 620 KB correct
23 Correct 23 ms 620 KB correct
24 Correct 20 ms 492 KB correct
25 Correct 1 ms 512 KB correct
26 Correct 21 ms 492 KB correct
27 Correct 24 ms 492 KB correct
28 Correct 4 ms 492 KB correct
29 Correct 2 ms 492 KB correct
30 Correct 40 ms 492 KB correct
31 Correct 38 ms 492 KB correct
32 Correct 44 ms 492 KB correct
33 Correct 38 ms 492 KB correct
34 Incorrect 2814 ms 2668 KB WA in grader: NO
35 Halted 0 ms 0 KB -