oj.uz

Submission #269211

# Submission time Handle Problem Language Result Execution time Memory
269211 2020-08-17T05:44:13 Z Autoratch Tropical Garden (IOI11_garden) C++14
49 / 100
 16 ms 15044 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5;
 
vector<pair<int,int> > adj[N];
pair<int,int> ed[N << 1];
vector<int> res[N << 1];
queue<tuple<int,int,int,int> > q;
 
void bfs()
{
    while(!q.empty())
    {
        auto [u,p,id,cnt] = q.front();
        q.pop();
   //     if(res[id].size()>=40) continue;
        if(cnt>100) continue;
        if(u!=p and p==adj[u][0].second) res[id].push_back(cnt);
        if(id==-1 or adj[u][0].second==p)
        { 
            for(auto [w,v] : adj[u]) if(v!=p or adj[u].size()==1) q.push({v,u,w,cnt+1}); 
        }
        else if(adj[u][1].second==p)
        { 
            auto [w,v] = adj[u][0]; if(v!=p) q.push({v,u,w,cnt+1}); 
        }
    }
}
 
void dfs(int u,int p,int id,int cnt)
{
    q.push({u,p,id,cnt});
    bfs();
    return;
    if(res[id].size()>=5) return;
    res[id].push_back(cnt);
    if(id==-1 or adj[u][0].second==p)
    {
        for(auto [w,v] : adj[u]) if(v!=p or adj[u].size()==1) dfs(v,u,w,cnt+1);
    }
    else if(adj[u][1].second==p) 
    {
        auto [w,v] = adj[u][0];
        if(v!=p) dfs(v,u,w,cnt+1);
    }
}
 
void count_routes(int n,int m,int p,int r[][2],int q,int g[])
{
    for(int i = 0,j = 0;i < m;i++)
    {
        int a = r[i][0],b = r[i][1];
        ed[j] = {a,b};
        adj[a].push_back({j++,b});
        ed[j] = {b,a};
        adj[b].push_back({j++,a});
    }
    dfs(p,p,-1,0);
    for(int i = 0;i < q;i++)
    {
        int ans = 0;
        for(int j = 0;j < m*2;j++) for(int x : res[j]) if(x==g[i]) ans++;
        /*
        {
            if(res[j].size()>0 and res[j][0]==g[i]) ans++;
            else if(res[j].size()>2 and (g[i]-res[j][1])%(res[j][2]-res[j][1])==0) ans++;
        }
        */
        answer(ans);
        for(int j = 0;j < m*2;j++)
        {
            for(int k = 1;k+2 < res[j].size();k++) 
                assert(res[j][k+1]-res[j][k]==res[j][k+2]-res[j][k+1] and res[j][k+1]!=res[j][k]);
        }
    }
    return;
    for(int i = 0;i < m*2;i++) 
    {
        cout << ed[i].first << ' ' << ed[i].second << endl;
        for(int x : res[i]) cout << x << ' ' ;
        cout << endl;
    }
    
}

Compilation message

garden.cpp: In function 'void bfs()':
garden.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |         auto [u,p,id,cnt] = q.front();
      |              ^
garden.cpp:24:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |             for(auto [w,v] : adj[u]) if(v!=p or adj[u].size()==1) q.push({v,u,w,cnt+1});
      |                      ^
garden.cpp:28:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |             auto [w,v] = adj[u][0]; if(v!=p) q.push({v,u,w,cnt+1});
      |                  ^
garden.cpp: In function 'void dfs(int, int, int, int)':
garden.cpp:42:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for(auto [w,v] : adj[u]) if(v!=p or adj[u].size()==1) dfs(v,u,w,cnt+1);
      |                  ^
garden.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         auto [w,v] = adj[u][0];
      |              ^
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:75:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for(int k = 1;k+2 < res[j].size();k++)
      |                           ~~~~^~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 11 ms 14592 KB Output is correct
3 Correct 11 ms 14592 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 12 ms 14464 KB Output is correct
6 Correct 11 ms 14592 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 14 ms 14592 KB Output is correct
9 Correct 16 ms 15044 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 11 ms 14592 KB Output is correct
3 Correct 11 ms 14592 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 12 ms 14464 KB Output is correct
6 Correct 11 ms 14592 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 14 ms 14592 KB Output is correct
9 Correct 16 ms 15044 KB Output is correct
10 Incorrect 10 ms 14464 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 11 ms 14592 KB Output is correct
3 Correct 11 ms 14592 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 12 ms 14464 KB Output is correct
6 Correct 11 ms 14592 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 14 ms 14592 KB Output is correct
9 Correct 16 ms 15044 KB Output is correct
10 Incorrect 10 ms 14464 KB Output isn't correct
11 Halted 0 ms 0 KB -