제출 #359251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
359251		beksultan04	Simurgh (IOI17_simurgh)	C++14	30 / 100	3063 ms	6620 KiB

simurgh

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30